Sütun Oluşturma algoritması
Sütun oluşturma algoritması ile bir VRP çözmek istiyorum. Sorunun amacı, sürekli olarak en aza indirmektir. ancak her düğümde aracın varış zamanının hesaplanmasında bir nokta vardır. araç yukarıda belirtilen VRP çözülmeden önce rotası önceden belirlenmiş bir tren gibi başka bir ulaşım modu ile senkronize edilmelidir. Tren, aracın geçeceği bazı noktalardan geçebilir ve bu noktalarda varış süresi, tren ve aracın varış saatinin maksimumudur. Fiyatlandırma alt problemini nasıl çözmem gerektiğini bilmek istiyorum?
Yanıtlar
Sorununuzu doğru anladıysam, ilk sürümle (tren olmadan) tek fark, zaman işlevinin toplayıcı olmamasıdır.
Örneğin, trenin düğümden geçtiğini varsayalım $j$ (verilen) zamanda $t_j$ve bir yol hesaplıyorsun $p$ kimin son düğümü $i$. Bu yoldaki toplam birikmiş süre şu şekilde gösterilir:$\tau_p(i)$. $\Delta t_{ij}$ aracın gitmesi için geçen süreyi gösterir $i$ -e $j$. Yolu genişletmek ve düğüm eklemek istiyorsanız$j$, ardından yol için toplam birikmiş süre $p$, $\tau_p$aşağıdaki şekilde artırılır: $$ \tau_p(j) := \max\{ t_j, \tau_p(i) + \Delta t_{ij} \} $$
Tren araçtan önce gelirse toplam süre değer alır $\tau_p(i) + \Delta t_{ij}$aksi takdirde değer alır $t_j$.
Bunun tren düğümlerinizde yalnızca daha düşük bir sınırla zaman pencerelerine sahip olmaya benzediğini unutmayın: yalnızca zaman pencereleri ekleyebilirsiniz. $[t_j, +\infty[$ düğümde $j$ ve en kısa yol algoritmanızı zaman pencereleri ile çalıştırın (eğer elinizde varsa).
Başka bir deyişle, (zaman) kaynak genişletme işlevi eklemeli değildir. Bu, örneğin , kendi özelleştirilmiş kaynak uzantısı kuralınızı girebileceğiniz kaynak kısıtlamalarıyla en kısa yolları hesaplayan harika bir python kitaplığı olan cspy tarafından ele alınır ( böyle bir örneğin verildiği belgelere bakın ). VRPy , VRP bir ARP piton kütüphanesi dayanır cspy kolon üretimi için kısa yolları hesaplamak için. VRPy zaman pencerelerini işlediğinden, kendinize iyi bir başlangıç noktası edindiniz!