Zaman pencereli ve değişken başlama zamanlı bir araç rotalama problemi için sütun türetme temelli mat-sezgiseller

Yıl 2019, Cilt: 34 Sayı: 4, 2061 - 2078, 25.06.2019

Hande Küçükaydın

https://doi.org/10.17341/gazimmfd.421828

Öz

Bu çalışmada, araçların kullanıldıkları süreye bağlı maliyetlerin oluştuğu ve araçların depodan başlama zamanının
bir karar verici tarafından belirlendiği zaman pencereli bir araç rotalama
problemi ele alınmaktadır. Problemi etkin bir şekilde çözmek için biri
yinelemeli yerel arama meta-sezgiselinden, diğeri değişken komşuluk arama
meta-sezgiselinden yararlanan iki sütun türetme temelli mat-sezgisel
geliştirilmiştir.  Geliştirilen
mat-sezgiseller literatürden alınarak türetilen 87 örnek üzerinde her
mat-sezgisel her örnekte 3 kere koşularak test edilmiştir.  Bilgisayımsal sonuçlar iki mat-sezgiselin de
etkinliğini kanıtlamış, ancak değişken komşuluk arama meta-sezgiseli kullanan
mat-sezgiselin daha başarılı olduğunu göstermiştir. Bu sayede kesin bir
yöntemle makul bir ana işlemci zamanında çözülemeyen büyük ölçülü problemler için
çok kısa bir zaman içerisinde iyi bir olurlu çözüm elde etmek mümkün hale
gelmiştir.

Anahtar Kelimeler

Zaman pencereli araç rotalama problemi, rota süresi, sütun türetme, mat-sezgiseller

Kaynakça

• Toth P. ve Vigo D., Vehicle Routing: Problems, Methods, and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2014.
• Ceselli A., Righini G., Salani M., A column generation algorithm for a rich vehicle routing problem, Transportation Science, 43 (1), 56-69, 2009.
• Desaulniers G., Madsen O.B., Ropke S., The Vehicle Routing Problem With Time Windows, Vehicle Routing: Problems, Methods, and Applications, Editörler: Toth P. ve Vigo D., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 119-159, 2014.
• Liberatore F., Righini G., Salani M.A., A column generation algorithm for the vehicle routing problem with soft time windows, 4OR A Quarterly Journal of Operations Research, 9 (1), 49-82, 2011.
• Bettinelli A., Ceselli A., Righini G., A branch-and-cut-and-price algorithm for the multi-depot heterogenous vehicle routing problem with time Windows, Transportation Research Part C, 19 (5), 723-740, 2011.
• Dabia S., Ropke S., van Woensel T., De Kok T., Branch and price for the time-dependent vehicle routing problem with time windows, Transportation Science, 47 (3), 380-396, 2013.
• Savelsbergh M.W.P., The vehicle routing problem with time windows: Minimizing route duration, ORSA Journal On Computing, 4 (2), 146-154, 1992. 8.
• Ioachim I, Gélinas S., Soumis F., Desrosiers J., A dynamic programming algorithm for the shortest path problem with time windows and linear node costs, Networks, 31 (3), 193-204, 1998.
• Desaulniers G., Villeneuve D., The shortest path problem with time windows and linear waiting costs, Transportation Science, 34 (3), 312-319, 2000.
• Archetti C., Speranza M.G., A survey on matheuristics for routing problems, EURO Journal on Computational Optimization, 2 (4), 223-246, 2014.
• Desaulniers G., Desrosiers J., Ioachim I., Solomon M. M., Soumis F., Villeneuve D., A unified framework for deterministic time constrained vehicle routing and crew scheduling problems, Fleet Management and Logistics, Editörler: Crainic T.G. ve Laporte G., Kluwer, Boston, 57-93, 1998.
• Desrosiers J. ve Lübbecke M.E., A primer in column generation, Column Generation, Editörler: Desaulniers G., Desrosiers J., Solomon M.M., Springer, New York, 1-32, 2005.
• Lübbecke M.E., Desrosiers J., Selected topics in column generation, Operations Research, 53 (6), 1007-1023, 2005.
• Gutiérrez-Jarpa G., Desaulniers G., Laporte G., Marianov V., A branch-and-price algorithm for vehicle routing problem with deliveries, selective pickups and time windows, European Journal of Operational Research, 206 (2), 341-349, 2010.
• Salani M. ve Vacca I., Branch and price for the vehicle routing problem with discrete split deliveries and time windows, European Journal of Operational Research, 213 (3), 470-477, 2011.
• Desaulniers G., Lessard F., Hadjar A., Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows, Transportation Science, 42 (3), 387-404, 2008.
• Feillet D., A tutorial on column generation and branch-and-price for vehicle routing problems, 4OR A Quarterly Journal of Operations Research, 8 (4), 407-424, 2010.
• Azi N., Gendreau M., Potvin J.-Y., An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, European Journal of Operational Research,, 202 (3), 756-763, 2010.
• Boschetti M., Maniezzo V., Roffilli M., Röhler A.B., Matheuristics: Optimization, simulation and control, Hybrid Metaheuristics, Lecture Notes in Computer Science 6373, Editörler: Blesa M., Blum C., Raidl G., Roli A., Sampels M., Springer Berlin Heidelberg, 171-177, 2010.
• Danna E. ve Pape C., Branch-and-price heuristics: a case study on the vehicle routing problem with time windows, Column Generation, Editörler: Desaulniers G., Desrosiers J., Solomon M.M., Springer, ABD, 99-129, 2005.
• Archetti C., Bianchessi N., Speranza M.G., A column generation approach for the split delivery vehicle routing problem, Networks, 58 (4), 241-254, 2011.
• Archetti C., Bianchessi N., Speranza M.G., The capacitated team orienteering problem with incomplete service, Optimization Letters, 7 (7), 1405-1417, 2013.
• Archetti C., Bianchessi N., Speranza M.G., Optimal solutions for routing problems with profits, Discrete Applied Mathematics, 161 (4-5), 547-557, 2013.
• Archetti C., Bianchessi N., Hertz A., Speranza M.G., Incomplete service and split deliveries in a routing problem with profits, Networks, 63 (2), 135-145, 2014.
• Archetti C., Bianchessi N., Hertz A., Speranza M.G., The split delivery capacitated team orienteering problem, Networks, 63 (1), 16-33, 2014.
• Aghezzaf E-H, Raa B., Landeghem H.V., Modeling inventory routing problems in supply chains of high consumption products, European Journal of Operational Research, 169 (3), 1048-1063, 2006.
• Raa B., Aghezzaf E.-H., Designing distribution patterns for long-term inventory routing with constant demand rates, International Journal of Production Economics, 112 (1), 255-263, 2008.
• Raa B., Aghezzaf E.-H., A practical solution approach for the cyclic inventory routing problem, European Journal of Operational Research, 192 (2), 429-441, 2009.
• Parragh S. N., Cordeau J.F., Doerner K. F., Hartl R. F., Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints, OR Spectrum, 34 (3), 593-633, 2012.
• Parragh S. N. ve Schmid V., Hybrid column generation and large neighborhood search for the dial-a-ride problem, Computers and Operations Research, 40 (1), 490-497, 2013.
• Cacchiani V., Hemmelmayr V. C., Tricoire F., A set covering based heuristic algorithm for the periodic vehicle routing problem, Discrete Applied Mathematics, 163 (1), 53-64, 2014.
• Dror M., Note on the complexity of the shortest path models for column generation in VRPTW, Operations Research, 42 (5), 977-978, 1994.
• Raidl G. R., Puchinger J., Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization, Hybrid Metaheuristics: An Emerging Approach to Optimization, Editörler: Blum C., Blesa M., Roli A., Sampels M., Springer Berlin Heidelberg, 31-62, 2008.
• Talbi E.-G., Metaheuristics: From Design to Implementation, New Jersey, Wiley, 2009.
• Glover F., Kochenberger G. A., Handbook of Metaheuristics, Dordrecht, Kluwer Academic Publishers, 2003.
• Cuervo D.P., Goos P., Sörensen K., Arráiz E., An iterated local search algorithm for the vehicle routing problem with backhauls, 237 (2), 454-464, 2014.
• Hansen P., Mladenovic N., Perez J.A.M., Variable neighborhood search: methods and applications, Annals of Operations Research, 175 (1), 367-407, 2010.
• Parragh S.N., Schmid V., Hybrid column generation and large neighborhood search for the dial-a-ride problem, Computers and Operations Research, 40 (1), 490-497, 2013.
• Solomon M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35 (2), 254-265, 1987.