Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm

This paper addresses a Time Dependent Capacitated Vehicle Routing Problem with stochastic vehicle speeds and environmental concerns. The problem has been formulated as a Markovian Decision Process. As distinct from the traditional attempts on the problem, while estimating the amount of fuel consumption and emissions, the model takes time-dependency and stochasticity of the vehicle speeds into account. The Time Dependent Capacitated Vehicle Routing Problem is known to be non-deterministic polynomial-time (NP)-Hard for even deterministic settings. Incorporating uncertainty to the problem increases complexity, which renders classical optimization methods infeasible. Therefore, the authors propose an Approximate Dynamic Programming based heuristic as a decision aid tool for the problem. The proposed Markovian Decision Model and Approximate Dynamic Programming based heuristic are flexible in terms that more environmentally friendly solutions can be obtained by changing the objective function from cost minimization to emissions minimization. The added values of the proposed decision support tools have been shown through computational analyses on several instances. The computational analyses show that incorporating vehicle speed stochasticity into decision support models has potential to improve the performance of resulting routes in terms of travel duration, emissions and travel cost. In addition, the proposed heuristic provides promising results within relatively short computation times.

• Record URL:
  https://doi.org/10.1016/j.trd.2017.04.016
• Record URL:
  http://www.sciencedirect.com/science/article/pii/S1361920916305284
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/13619209
• Supplemental Notes:
  • Abstract reprinted with permission of Elsevier.
• Authors:
  • Çimen, Mustafa
  • Soysal, Mehmet
• Publication Date: 2017-7

Language

• English

Media Info

• Media Type: Web
• Features: Appendices; Figures; References; Tables;
• Pagination: pp 82-98
• Serial:
  • Transportation Research Part D: Transport and Environment
  • Volume: 54
  • Publisher: Elsevier
  • ISSN: 1361-9209
  • Serial URL: http://www.sciencedirect.com/science/journal/13619209

Subject/Index Terms

• TRT Terms: Delivery service; Dynamic programming; Markov processes; Routing; Speed; Stochastic processes; Sustainable transportation; Time windows
• Uncontrolled Terms: Vehicle routing problem
• Subject Areas: Environment; Freight Transportation; Highways; Operations and Traffic Management; Planning and Forecasting;

Filing Info

• Accession Number: 01642776
• Record Type: Publication
• Files: TRIS
• Created Date: Jul 31 2017 4:32PM