Multi-vehicle one-to-one pickup and delivery problem with split loads

Abstract

Bu çalışmada Parçalanabilir Yüklü Toplama ve Dağıtma Araç Rotalama Problemi (MPDPSL)ele alınmıştır. Bu problem, bire bir Toplama ve Dağıtma Probleminin bir yükün farklıaraçlar tarafından ya da bir araç tarafından birden çok seferde sağlanabildiği bir uzantısıdır.Uygulamada, yükün fiziksel olarak parçalanabildiği alanlarda, parçalanabilir dağıtım geçerlibir seçenek olarak 3. taraf lojistik işletmelerinin kurye servislerinde kullanılmaktadır.Aynı zamanda bu problemin, yüklerin sabit bir maliyet tarafından dışarıdan bir firmatarafından taşınabildiği (MPDPSL-O) ve rotaların depo olmadan döngüsel olduğu (MPDPSLC)iki varyantı ele alınmıştır. Problemin ve iki varyantının çözümünde tabu arama vebenzetimli tavlamanın güçlü yönlerini buluşturan bir sezgisel algoritma geliştirilmiştir.Yazında yer alan bir problem kümesi üzerinde yapılan deneyler sonucunda, sezgiselinmakul sürelerde iyi sonuçlar verdiği saptanmıştır. Yazındaki başka bir problem kümesiiçin ise ilk sonuçlar ortaya konmuştur ve parçalanabilir yükün dağıtım ağının yapısınabağlı olarak sağladığı faydalar incelenmiştir. Çeşitli maliyet yapıları altında dışarıdanteminin potansiyel faydalarını incelemek amacıyla MPDPSL ve MPDPSL-O karşılaştırılmıştır.Son olarak, MPDPSL-C için gerçek bir vaka çözülmüştür.

In this study, we consider the Multi-vehicle One-to-one Pickup and Delivery Problemwith Split Loads (MPDPSL). This problem is a generalization of the one-to-one Pickupand Delivery Problem (PDP) where each load can be served by multiple vehicles as wellas multiple stops by the same vehicle. In practice, split deliveries is a viable option inmany settings where the load can be physically split, such as courier services of thirdparty logistics operators. We also consider two other variants of the problem where itis possible to outsource the pickup and delivery requests for a fixed charge (MPDPSLO)and where the routes are cyclic without depot (MPDPSL-C). We propose an efficientheuristic that combines the strengths of Tabu Search and Simulated Annealing for thesolution of MPDPSL and its variants. Results from experiments on a problem set inthe literature indicate that the heuristic is capable of producing good quality solutionsin reasonable time, we present first results on another problem set in the literature anddiscuss the merits of load splitting with respect to the network distribution. We comparethe results of MPDPSL and MPDPSL-O in order to illustrate the potential benefits ofoutsourcing under various outsourcing cost schemes. Finally, we present a solution for areal life case of MPDPSL-C.