A column generation-based matheuristic for an inventory-routing problem with driver-route consistency

被引：0
作者：
Najy, Waleed [1 ]
Archetti, Claudia [2 ]
Diabat, Ali [1 ,3 ]
机构：
[1] Division of Engineering, New York University Abu Dhabi, Saadiyat Island, Abu Dhabi
[2] Department of Economics and Management, University of Brescia, Contrada Santa Chiara 50, Brescia
[3] Department of Civil and Urban Engineering, Tandon School of Engineering, New York University, Brooklyn
来源：
European Journal of Operational Research | 2025年 / 324卷 / 02期
关键词：
Column generation; Driver consistency; Fixed routes; Inventory routing problems; Matheuristic algorithms;
D O I：
10.1016/j.ejor.2025.02.007
中图分类号：
学科分类号：
摘要：
This paper investigates a variant of an inventory-routing problem (IRP) that enforces two conditions on the structure of the solution: time-invariant routes, and a fixed, injective (i.e., one-to-one) assignment of routes to vehicles. The practical benefits of concurrent route invariance and driver assignments are numerous. Fixed routes reduce the solution space of the problem and improve its tractability; they simplify operations; and they increase the viability of newer delivery technologies like drones and autonomous vehicles. Consistency between driver and customer is linked to improved service, driver job satisfaction and delivery efficiency, and is also an important consideration in certain contexts like home healthcare. After formulating the problem as a mixed integer-linear program, we recast it as a set partitioning problem whose linear relaxation is solved via column generation. Due to the prohibitively expensive nature of the pricing problem that generates new columns, we present a novel column generation-based heuristic for it that relies on decoupling routing and inventory management decisions. We demonstrate the effectiveness of the proposed method via a numerical study. © 2025 Elsevier B.V.
引用
收藏
页码：382 / 397
页数：15
相关论文
共 53 条
  • [1] Adulyasak Y., Cordeau J.-F., Jans R., Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems, INFORMS Journal on Computing, 26, 1, pp. 103-120, (2014)
  • [2] Albinski S., Crainic T.G., Minner S., The day-before truck platooning planning problem and the value of autonomous driving, (2020)
  • [3] Amazon-MIT S., Amazon last-mile routing research challenge, (2021)
  • [4] Archetti C., Bertazzi L., Hertz A., Speranza M.G., A hybrid heuristic for an inventory routing problem, INFORMS Journal on Computing, 24, 1, pp. 101-116, (2012)
  • [5] Archetti C., Bertazzi L., Laporte G., Speranza M.G., A branch-and-cut algorithm for a vendor-managed inventory-routing problem, Transportation Science, 41, 3, pp. 382-391, (2007)
  • [6] Archetti C., Boland N., Speranza M.G., A matheuristic for the multivehicle inventory routing problem, INFORMS Journal on Computing, 29, 3, pp. 377-387, (2017)
  • [7] Archetti C., Ljubic I., Comparison of formulations for the inventory routing problem, European Journal of Operational Research, 303, 3, pp. 997-1008, (2022)
  • [8] Baldacci R., Mingozzi A., Roberti R., New route relaxation and pricing strategies for the vehicle routing problem, Operations Research, 59, 5, pp. 1269-1283, (2011)
  • [9] Bard J.F., Nananukul N., A branch-and-price algorithm for an integrated production and inventory routing problem, Computers & Operations Research, 37, 12, pp. 2202-2217, (2010)
  • [10] Bell W.J., Dalberto L.M., Fisher M.L., Greenfield A.J., Jaikumar R., Kedia P., Mack R.G., Prutzman P.J., Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer, Interfaces, 13, 6, pp. 4-23, (1983)
123456