Constrained Local Search for Last-Mile Routing

Last-mile routing refers to the final step in a supply chain, delivering packages from a depot station to the homes of customers. At the level of a single van driver, the task is a traveling salesman problem. But the choice of route may be constrained by warehouse sorting operations, van-loading processes, driver preferences, and other considerations rather than a straightforward minimization of tour length. The authors propose a simple and efficient penalty-based local search algorithm for route optimization in the presence of such constraints, adopting a technique developed by Helsgaun to extend the Lin–Kernighan–Helsgaun algorithm for the traveling salesman problem to general vehicle routing problems. The authors apply their technique to handle combinations of constraints obtained from an analysis of historical routing data, enforcing properties that are desired in high-quality solutions. The authors' code is available under the open-source Massachusetts Institute of Technology license. An earlier version of the code received the $100,000 top prize in the Amazon Last Mile Routing Research Challenge organized in 2021.

• Record URL:
  • https://doi.org/10.1287/trsc.2022.1185
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Supplemental Notes:
  • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
• Authors:
  • Cook, William
  • Held, Stephan
  • Helsgaun, Keld
• Publication Date: 2024-1

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: pp 12-26
• Serial:
  • Transportation Science
  • Volume: 58
  • Issue Number: 1
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Delivery service; First mile and last mile; Optimization; Routing; Traveling salesman problem
• Subject Areas: Freight Transportation; Operations and Traffic Management; Planning and Forecasting;

Filing Info

• Accession Number: 01906787
• Record Type: Publication
• Files: TRIS
• Created Date: Feb 5 2024 9:34AM