A Simulated Annealing algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Maximum Tour Time Length

Publish Year: 1391
نوع سند: مقاله کنفرانسی
زبان: English
View: 1,426

This Paper With 7 Page And PDF Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

IIEC08_100

تاریخ نمایه سازی: 7 آذر 1391

Abstract:

The Vehicle Routing Problem with Simultaneous Pick-up and Delivery (VRPSPD) and maximum time limit for traversing of each tour is a variant of the classicalvehicle routing problem (VRP) where customers require simultaneous delivery and pick-up. Deliveries are supplied from a single depot at the beginning of the vehicle'sservice, while pick-up loads are taken to the same depot at the end of the service. Also time of traversing of each routeshould not encroach the specified limit. In this research, the aforesaid problem was introduced and a mixed integer programming model was developedfor it. Because of being NP-Hard and the impossibility of solving it in the large instances, a simulated annealing algorithm was developed to handle the problem. Forproducing the initial solution for this algorithm, two methods were built. Furthermore, four procedures forimproving the solution were developed, which three ofthem are being used for inter-route and the other one for intra-route improvement. Computational results were reported for 26 produced test problems of the size between 5 to 200 customers.

Keywords:

Vehicle Routing Problem , Simultaneous Pickup and Delivery , Maximum tour time length , Heuristic , Simulated Annealing

Authors

Milad Keshvari Fard

Sharif University of Technology

Laleh Asadi

Shiraz University