Column generation based hybrid optimization method for last-mile delivery service with autonomous vehicles

Hongjian Hu, Hu Qin, Gangyan Xu, Nan Huang, Peiyang He

Research output: Journal article publicationJournal articleAcademic researchpeer-review


The research addresses the Last-Mile Delivery Service with Autonomous Vehicles (LMS-AV), which focuses on the multiple trips made by autonomous vehicles (AVs). This feature, widely utilized in real-world applications, has the potential to not only reduce the number of required vehicles and drivers but also lower operating costs. Recognizing these benefits as opportunities, we aim to enhance these advantages further. To this end we propose a novel branch-and-price-and-cut (BPC) algorithm based on the trip-based set partitioning model. Additionally, building upon the BPC algorithm, a column generation (CG) based heuristic algorithm is built to solve larger size instances. This model utilizes a two-phase CG algorithm to solve the linear relaxation sub-problem. A label-setting algorithm is tailored to generate feasible paths, and we introduce a strategy, named ’Finding A Time Point to Minimize the Reduced Cost of A Path’ to identify trips with minimal reduced costs. Furthermore, k-path and subset-row inequalities are introduced to tighten the relaxation gap. To accelerate the sub-problem's solution process, we propose several methods, including bidirectional search techniques, heuristic labeling, completion bounds, and ng-route relaxation. Results indicate that our BPC algorithm can solve instances with up to 100 customers, and our heuristic algorithm not only efficiently solves all instances but also maintains a minimal gap when compared to the BPC algorithm.

Original languageEnglish
Article number102549
JournalAdvanced Engineering Informatics
Publication statusPublished - Aug 2024


  • Autonomous vehicles
  • Branch-and-price-and-cut
  • Column generation
  • Last-mile

ASJC Scopus subject areas

  • Information Systems
  • Artificial Intelligence


Dive into the research topics of 'Column generation based hybrid optimization method for last-mile delivery service with autonomous vehicles'. Together they form a unique fingerprint.

Cite this