Boyutlar

Rota çözücü, bir aracın rotası boyunca toplanan ve seyahat süresi veya araç teslim alma ve teslimat yapıyorsa taşıdığı toplam ağırlık gibi hacimleri izlemek için boyut adlı bir nesne kullanır. Bir yönlendirme sorunu, kısıtlamaların veya hedef işlevin söz konusu miktarını içeriyorsa bu durumu belirtmek için bir boyut tanımlamanız gerekir.

Bu bölümde boyutların nasıl tanımlanacağı ve kullanılacağı açıklanmaktadır.

Boyut örnekleri

Önceki bölümlerden boyutlara ait birkaç örneği burada bulabilirsiniz.

  • VRPTW örneği, her bir aracın kümülatif seyahat süresini izlemek için bir boyut oluşturur. Çözücü, aracın yalnızca konumun zaman aralığı içindeki bir konumu ziyaret etmesine ilişkin kısıtlamayı uygulamak için boyutu kullanır.

  • CVRP örneği, talepler (ör.teslim alınacak paketlerin ağırlığı veya hacmi) için bir boyut oluşturur. Bu boyut, aracın rotası boyunca taşıdığı toplu yükü izler. Çözücü, aracın kapasitesinin kapasiteyi aşamadığı kısıtlamayı uygulamak için boyutu kullanır.

Aşağıdaki örneklerde AddDimension yöntemi kullanılarak VRPTW için bir boyut tanımlanmaktadır.

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

C#

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

AddDimension yönteminde aşağıdaki girişler bulunur:

  • callback_index: Miktarı döndüren geri çağırma için dizin. Çözümleyicinin geri çağırmaya dahili referansı olan dizin, RegisterTransitCallback veya RegisterUnitaryTransitCallback gibi yöntemlerle oluşturulur.
  • slack_max: Konumlardaki bekleme sürelerini temsil etmek için kullanılan bir değişken olan Sack için maksimum değer. Ayrıntılar için aşağıdaki kaydırma değişkenlerine bakın. Sorun bekleme süresini içermiyorsa genellikle slack_max değerini 0 olarak ayarlayabilirsiniz.
  • capacity: Rota boyunca toplanan toplam miktar için maksimum değer. CVRP'deki gibi kısıtlamalar oluşturmak için capacity özelliğini kullanın. Sorununuz böyle bir kısıtlama içermiyorsa capacity'yi, rotalara herhangi bir kısıtlama uygulamayacak kadar büyük bir değere (örneğin, geri çağırmayı tanımlamak için kullanılan matris veya dizideki tüm girişlerin toplamı) belirleyebilirsiniz.
  • fix_start_cumulative_to_zero: Boole değeri. Bu değer doğruysa miktarın kümülatif değeri 0'dan başlar. Çoğu durumda bu seçenek True olarak ayarlanmalıdır. Bununla birlikte, VRPTW veya kaynak kısıtlamaları ile ilgili sorunlar için bazı araçların zaman aralığı kısıtlamaları nedeniyle 0'dan sonra başlaması gerekebilir. Bu nedenle, bu sorunlar için fix_start_cumulative_to_zero değerini False olarak ayarlamanız gerekir.
  • dimension_name: Boyutun adı (ör. 'Distance'), programın başka bir yerinde değişkenlere erişmek için kullanabileceğiniz dizedir.

CVRP programı, AddDimensionWithVehicleCapacity yöntemini kullanarak biraz farklı bir boyut türü oluşturur. Bu yöntem bir dizi kapasite alır ve her araç için bir giriş içerir. (Bunun aksine AddDimension, capacity için tek bir değer aldığından tüm araçların aynı kapasiteye sahip olduğu varsayılır.)

Boyut oluşturan diğer yöntemler için RoutingModel referans sayfasına bakın.

Çözüm zaman aralıklarını bir listeye veya diziye kaydetme bölümü, kümülatif verileri bir liste veya dizideki boyuta kaydeden işlevleri sunar.

Slack değişkenleri

Aşağıda, seyahat süresiyle ilgili bir sorun için slack değişkenlerini gösteren bir örnek verilmiştir. Bir aracın, rotasının bir adımında i konumundan j konumuna gittiğini varsayalım ve:

  • Aracın i'de toplu seyahat süresi 100 dakikadır.
  • Aracın j'deki toplu seyahat süresi 200 dakikadır.
  • i'den j'ye seyahat süresi 75 dakika.

Araç, varış noktasında i konumundan hemen ayrılamaz veya j konumunda kümülatif süre 175 olur. Bunun yerine, aracın yola çıkmadan önce i konumu için 25 dakika beklemesi, diğer bir deyişle i konumundaki bindirme 25 dakika beklemelidir.

Zaman aralığı kısıtlamaları nedeniyle araçların bir konumu ziyaret etmeden önce beklemesi gerekebileceğinden VRPTW'da kaymaya izin vermeniz gerekir. Böyle bir problemde, araçların bir sonraki konuma geçmeden önce bir konumda beklemelerine izin vermek istediğiniz maksimum süreyi slack_max olarak ayarlayın. Ne kadar bekledikleri önemli değilse slack_max öğesini çok büyük bir sayıya ayarlayın.

Diğer yandan CVRP için, birikimli yükteki i - j değişimi i talebe her zaman eşittir. Bu nedenle, aynı düzeydedir. Bunun gibi sorunlar için slack_max öğesini 0 olarak ayarlayabilirsiniz.

Şimdi de slack'in resmi tanımını vereceğiz. Dahili olarak bir boyut, rotalar genelinde biriken miktarlarla ilgili iki tür değişken depolar:

  • Toplu taşıma değişkenleri: Bir rotanın her adımındaki miktar artışı veya azalması. i -> j bir rotadaki bir adımsa, toplu taşıma değişkeni, toplu taşıma matrisinin i ve j şeklinde bir giriştir (bir toplu taşıma geri çağırması için) veya yalnızca i konumundaki geri çağırma değeri (geri çağırma yalnızca bir konuma bağlıysa).
  • Kümülatif değişkenler: Her konumda biriken toplam miktar. Kümülatif değişkene dimension_name.CumulVar(i) konumunda i konumunda erişebilirsiniz. Bir örnek için VRPTW örneğindeki zaman aralığı kısıtlamalarına bakın.

Bir aracın tek bir adımla i konumundan j konumuna gittiğini varsayarsak, bu bağımsız değişken aşağıdaki değişkenlerle ilgilidir: 

slack(i) = cumul(j) - cumul(i) - transit(i, j)

Boyutlar hakkında daha fazla bilgi için referans bölümünde RoutingDimension bölümüne bakın.