A heuristic with a performance guarantee for the commodity constrained split delivery vehicle routing problem

作者
Matteo Petris,Claudia Archetti,Diego Cattaruzza,Maxime Ogier,Frédéric Semet
出处
期刊:Networks [Wiley]
卷期号:84 (4): 446-464 被引量:10
标识
DOI:10.1002/net.22238
摘要

Abstract The commodity constrained split delivery vehicle routing problem (C‐SDVRP) is a routing problem where customer demands are composed of multiple commodities. A fleet of capacitated vehicles must serve customer demands in a way that minimizes the total routing costs. Vehicles can transport any set of commodities and customers are allowed to be visited multiple times. However, the demand for a single commodity must be delivered by one vehicle only. In this work, we developed a heuristic with a performance guarantee to solve the C‐SDVRP. The proposed heuristic is based on a set covering formulation, where the exponentially‐many variables correspond to routes. First, a subset of the variables is obtained by solving the linear relaxation of the formulation by means of a column generation approach which embeds a new pricing heuristic aimed to reduce the computational time. Solving the linear relaxation gives a valid lower bound used as a performance guarantee for the heuristic. Then, we devise a restricted master heuristic to provide good upper bounds: the formulation is restricted to the subset of variables found so far and solved as an integer program with a commercial solver. A local search based on a mathematical programming operator is applied to improve the solution. We test the heuristic algorithm on benchmark instances from the literature. The comparison with the state‐of‐the‐art heuristics for solving the C‐SDVRP shows that our approach significantly improves the solution time, while keeping a comparable solution quality and improving some best‐known solutions. In addition, our approach is able to solve large instances with 100 customers and six commodities, and also provides very good quality lower bounds. Furthermore, an instance of the C‐SDVRP can be transformed into a CVRP instance by simply duplicating each customer as many times as the requested commodities and by assigning as demand the demand of the single commodity. Hence, we compare heuristics for the C‐SDVRP against the state‐of‐the‐art heuristic for the Capacitated Vehicle Routing Problem (CVRP). The latter approach revealed to have the best performance. However, our approach provides solutions of comparable quality and has the interest of providing a performance guarantee.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
聪慧的冷风完成签到,获得积分10
刚刚
谢逊完成签到,获得积分20
1秒前
crazy发布了新的文献求助10
1秒前
taka发布了新的文献求助10
1秒前
刘雨完成签到 ,获得积分10
1秒前
Mississippiecho完成签到,获得积分0
2秒前
turnsole发布了新的文献求助10
2秒前
Wayne完成签到,获得积分10
2秒前
bo发布了新的文献求助10
2秒前
小陈完成签到,获得积分10
3秒前
3秒前
火鸡味锅巴完成签到 ,获得积分10
3秒前
淡定采波完成签到,获得积分10
3秒前
落后的嚣完成签到,获得积分10
3秒前
GQ完成签到 ,获得积分10
4秒前
Preveil完成签到,获得积分10
4秒前
小周发布了新的文献求助10
4秒前
娜娜子完成签到 ,获得积分10
5秒前
xxszyb完成签到,获得积分10
6秒前
elysia完成签到,获得积分10
6秒前
6秒前
小蘑菇的应助被XY采纳,获得10
6秒前
ZZZ完成签到 ,获得积分10
7秒前
矜持完成签到,获得积分10
7秒前
雪糕发布了新的文献求助10
7秒前
大东东完成签到,获得积分10
7秒前
庾傀斗发布了新的文献求助10
7秒前
陈丰滢完成签到,获得积分10
7秒前
7秒前
颜夜关注了科研通微信公众号
8秒前
望望旺仔牛奶完成签到,获得积分10
9秒前
oldjeff完成签到,获得积分10
9秒前
Verna完成签到,获得积分10
10秒前
熊火焰完成签到,获得积分10
10秒前
zjxnq完成签到 ,获得积分10
10秒前
科研大大完成签到 ,获得积分10
10秒前
jzj完成签到 ,获得积分0
10秒前
风息完成签到,获得积分10
11秒前
鱼大大完成签到,获得积分10
11秒前
浮生若梦完成签到,获得积分10
11秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1500
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
John McDowells Bildungstheorie 800
八旗制度の研究 600
Analyses de reconnaissances de dettes passées devant les échevins d'Ypres (1249-1291) 600
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8159288
求助须知:如何正确求助?哪些是违规求助? 9554702
关于积分的说明 21720900
捐赠科研通 7748911
什么是DOI,文献DOI怎么找? 3427184
关于科研通互助平台的介绍 2552111
邀请新用户注册赠送积分活动 2471479