A Branch and Cut Algorithm for the Multi-Vehicle One-to-One Pickup and Delivery Problem with Split Loads

ÖNCAN T., TÜZÜN AKSU D., ŞAHİN G., Sahin M.

IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Singapore, Singapur, 6 - 09 Aralık 2011, ss.1864-1868 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/ieem.2011.6118238
  • Basıldığı Şehir: Singapore
  • Basıldığı Ülke: Singapur
  • Sayfa Sayıları: ss.1864-1868
  • Galatasaray Üniversitesi Adresli: Evet

Özet

In this work we deal with the Multi-vehicle One-to-one Pickup and Delivery Problem with Split Loads (MPDPSL). This problem is a generalization of the one-to-one Pickup and Delivery Problem (PDP) where each load can be served by multiple stops by the same vehicle. In practice split deliveries is a viable option in many settings such as courier services of third party logistics operators. We propose a branch-and-cut algorithm which employs valid inequalities devised for special cases of the MPDPSL, such as the Dial-a-Ride Problem, PDP and Split Delivery Vehicle Routing Problem. According to our computational experiments with randomly generated test instances, we may claim that the proposed algorithm can be used for small sized instances.