A column-and-row generation approach for the flying sidekick travelling salesman problem

旅行商问题 无人机 列生成 计算机科学 数学优化 卡车 车辆路径问题 水准点(测量) 代表(政治) 整数规划 运筹学 布线(电子设计自动化) 数学 工程类 计算机网络 遗传学 大地测量学 政治 法学 地理 政治学 生物 航空航天工程
作者
Maurizio Boccia,Adriano Masone,Antonio Sforza,Claudio Sterle
出处
期刊:Transportation Research Part C-emerging Technologies [Elsevier BV]
卷期号:124: 102913-102913 被引量:73
标识
DOI:10.1016/j.trc.2020.102913
摘要

The flying sidekick traveling salesman problem (FS-TSP) is a parcel delivery problem arising in the last-mile logistics, where the distribution plan of a driver-operated truck assisted by a drone (unmanned aerial vehicle, UAV) has to be defined. The FS-TSP is a variant of the TSP where routing decisions are integrated with customer-to-drone and customer-to-truck assignment decisions and truck-and-drone synchronization constraints. The objective is the minimization of the time required to serve all the customers, taking into account drone payload capacity and battery power constraints. In this work we provide a new representation of the FS-TSP based on the definition of an extended graph. This representation allows to model the problem by a new and compact integer linear programming formulation, where the synchronization issue is tackled in a column generation fashion, thus avoiding the usage of big-M constraints, representing one of the main drawbacks of the models present in literature. The proposed formulation has been solved by an exact approach which combines a Branch-and-Cut algorithm and a column generation procedure, strengthened by variable fixing strategies and new valid inequalities specifically defined for the problem. The proposed method has been experienced on a large set of benchmark instances. Computational results show that the proposed approach either is competitive or outperforms the best exact approach present in literature for the FS-TSP. Indeed, it is able to provide the optimal solution for all small size instances with 10 customers and for several medium size instances with 20 customers, some of them never solved before.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
PDF的下载单位、IP信息已删除 (2025-6-4)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
罗密欧与傅里叶完成签到,获得积分10
1秒前
微雨若,,完成签到 ,获得积分10
1秒前
gao发布了新的文献求助30
1秒前
dd33完成签到,获得积分10
2秒前
2秒前
所所应助何寒松采纳,获得10
2秒前
青衣北风发布了新的文献求助10
2秒前
鸡蛋发布了新的文献求助10
2秒前
2秒前
zzz完成签到,获得积分10
2秒前
3秒前
难过语蓉完成签到,获得积分10
3秒前
今后应助wenqing采纳,获得10
3秒前
林夕完成签到 ,获得积分10
3秒前
3秒前
yao chen完成签到,获得积分10
3秒前
刘刘完成签到,获得积分10
4秒前
4秒前
余慕康发布了新的文献求助10
4秒前
Incendio关注了科研通微信公众号
4秒前
CAAA完成签到,获得积分10
4秒前
5秒前
qiu文献发布了新的文献求助10
5秒前
5秒前
无聊的火龙果应助高灵雨采纳,获得20
5秒前
jenny发布了新的文献求助10
6秒前
科研通AI2S应助武坤采纳,获得10
6秒前
共享精神应助李秋秋采纳,获得10
7秒前
绝世冰淇淋完成签到 ,获得积分10
7秒前
SYLH应助自觉的黑夜采纳,获得10
7秒前
8秒前
万木完成签到,获得积分10
8秒前
科研通AI2S应助欢欢采纳,获得10
9秒前
9秒前
10秒前
Hello应助代舒宇采纳,获得10
10秒前
丶丶发布了新的文献求助10
10秒前
10秒前
Jasper应助乐正广山采纳,获得10
10秒前
妮妮完成签到 ,获得积分10
10秒前
高分求助中
A new approach to the extrapolation of accelerated life test data 1000
Cognitive Neuroscience: The Biology of the Mind 1000
Technical Brochure TB 814: LPIT applications in HV gas insulated switchgear 1000
Immigrant Incorporation in East Asian Democracies 600
Nucleophilic substitution in azasydnone-modified dinitroanisoles 500
不知道标题是什么 500
A Preliminary Study on Correlation Between Independent Components of Facial Thermal Images and Subjective Assessment of Chronic Stress 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 遗传学 基因 物理化学 催化作用 冶金 细胞生物学 免疫学
热门帖子
关注 科研通微信公众号,转发送积分 3968771
求助须知:如何正确求助?哪些是违规求助? 3513646
关于积分的说明 11169065
捐赠科研通 3249011
什么是DOI,文献DOI怎么找? 1794589
邀请新用户注册赠送积分活动 875236
科研通“疑难数据库(出版商)”最低求助积分说明 804740