A distributed VNS algorithm for optimizing dial-a-ride problems in large-scale scenarios

These days, transportation and logistic problems in large cities are demanding smarter transportation services that provide flexibility and adaptability. A possible solution to this arising problem is to compute the best routes for each new scenario. In this problem, known in the literature as the dial-a-ride problem, a number of passengers are transported between pickup and delivery locations trying to minimize the routing costs while respecting a set of prespecified constraints. This problem has been solved in the literature with several approaches from small to medium sized problems. However, few efforts have dealt with large scale problems very common in massive scenarios (big cities or highly-populated regions). In this study, a new distributed algorithm based on the partition of the requests space and the combination of the routes is presented and tested on a set of 24 different scenarios of a large-scale problem (up to 16,000 requests or 32,000 locations) in the city of San Francisco. The results show that, not only the distributed algorithm is able to solve large problem instances that the corresponding sequential algorithm is unable to solve in a reasonable time, but also to have an average improvement of 9% in the smaller problems. The results have been validated by means of statistical procedures proving that the distributed algorithm can be an effective way to solve high dimensional dial-a-ride problems.

• Record URL:
  • https://doi.org/10.1016/j.trc.2015.02.024
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S0968090X15000790
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/0968090X
• Supplemental Notes:
  • Abstract reprinted with permission of Elsevier.
• Authors:
  • Muelas, Santiago
  • LaTorre, Antonio
  • Peña, José-María
• Publication Date: 2015-5

Language

• English

Media Info

• Media Type: Digital/other
• Features: Appendices; Figures; Maps; References; Tables;
• Pagination: pp 110-130
• Serial:
  • Transportation Research Part C: Emerging Technologies
  • Volume: 54
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0968-090X
  • Serial URL: http://www.sciencedirect.com/science/journal/0968090X

Subject/Index Terms

• TRT Terms: Algorithms; Demand responsive transportation; Large cities; Optimization; Paratransit services; Routes and routing
• Geographic Terms: San Francisco (California)
• Subject Areas: Operations and Traffic Management; Public Transportation; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01560595
• Record Type: Publication
• Files: TRIS
• Created Date: Apr 17 2015 1:56PM