.png){kind=icon}
返回
Compact Formulations for Split Delivery Routing Problems
.png){kind=icon}
PRE
AI
DOI：10.1287/trsc.2021.1106.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Split delivery routing problems are concerned with serving the demand of a set of customers with a fleet of capacitated vehicles at minimum cost, where a customer can be served by more than one vehicle if beneficial. They generalize traditional variants of routing problems and have applications in commercial and humanitarian logistics. Previously, formulations involving only commonly used arc-based variables have provided only relaxations for split delivery variants, as the possibility of visiting customers more than once introduces modeling challenges. The only known compact formulations are based on variables indexed by vehicle or by visit number and perform poorly when using general-purpose integer programming software. We present compact formulations that avoid the use of these types of variables and that canmodel split delivery routing problemswith andwithout time windows. Computational experiments demonstrate their superior performance over existing compact formulations. We also develop a branch-and-cut algorithm that balances the efficiency derived froma relaxed formulationwith the strength derived fromone of the proposed formulations and demonstrate its efficacy on a large set of benchmark instances. The algorithmsolves 95 instances to proven optimality for the first time and improves the best known lower and/ or upper bound formany other instances.
Keyword:
vehicle routing
split delivery
compact models
branch-and-cut
期刊
IF:
4.8
论文数:
1.9K
被引数:
8.4K
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容