The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches

车辆路径问题 数学优化 拉格朗日松弛 布线(电子设计自动化) 极限(数学) 利用 整数规划 分支和切割 一般化 计算机科学 整数(计算机科学) 放松(心理学) 数学 心理学 计算机网络 数学分析 社会心理学 计算机安全 程序设计语言
作者
Claudio Gambella,Joe Naoum‐Sawaya,Bissan Ghaddar
出处
期刊:Informs Journal on Computing 卷期号:30 (3): 554-569 被引量:32
标识
DOI:10.1287/ijoc.2017.0800
摘要

This paper addresses a generalization of the vehicle routing problem in which the pick-up locations of the targets are nonstationary. We refer to this problem as the vehicle routing problem with floating targets and the main characteristic is that targets are allowed to move from their initial home locations while waiting for a vehicle. This problem models new applications in drone routing, ridesharing, and logistics where a vehicle agrees to meet another vehicle or a customer at a location that is away from the designated home location. We propose a Mixed Integer Second Order Cone Program (MISOCP) formulation for the problem, along with valid inequalities for strengthening the continuous relaxation. We further exploit the problem structure using a Lagrangian decomposition and propose an exact branch-and-price algorithm. Computational results on instances with varying characteristics are presented and the results are compared to the solution of the full problem using CPLEX. The proposed valid inequalities reduce the computational time of CPLEX by up to 30% on average while the proposed branch and price is capable of solving instances where CPLEX fails in finding the optimal solution within the imposed time limit.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
zhuangdreamgirl完成签到,获得积分10
刚刚
科研通AI6.1应助lin采纳,获得10
刚刚
拼搏诗翠发布了新的文献求助10
1秒前
Hello应助小白采纳,获得10
1秒前
情怀应助spyspy采纳,获得10
2秒前
SOTA完成签到,获得积分20
2秒前
隐形曼青应助乔满天采纳,获得10
2秒前
3秒前
4秒前
安小云发布了新的文献求助100
4秒前
5秒前
7秒前
iW关闭了iW文献求助
7秒前
Qiangzai完成签到,获得积分10
8秒前
111发布了新的文献求助10
8秒前
dldldldl应助Markov采纳,获得10
8秒前
8秒前
凶狠的姚完成签到 ,获得积分10
10秒前
小柴胡关注了科研通微信公众号
11秒前
无极微光应助稳重的衬衫采纳,获得20
12秒前
英俊的铭应助现代的书本采纳,获得10
12秒前
13秒前
Akim应助研友_LJGGqn采纳,获得10
13秒前
SOTA发布了新的文献求助10
13秒前
zsj97发布了新的文献求助10
13秒前
董董的完成签到,获得积分10
14秒前
FashionBoy应助niuma采纳,获得10
14秒前
wuhoo完成签到,获得积分10
14秒前
haidayu完成签到,获得积分10
14秒前
15秒前
15秒前
18秒前
FashionBoy应助inin采纳,获得10
19秒前
accept完成签到,获得积分20
20秒前
神勇尔蓝发布了新的文献求助10
20秒前
lizhaonian完成签到,获得积分10
20秒前
20秒前
加贝完成签到 ,获得积分10
22秒前
希望天下0贩的0应助756采纳,获得10
23秒前
天天快乐应助XXX采纳,获得10
23秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
Handbook of pharmaceutical excipients, Ninth edition 5000
Aerospace Standards Index - 2026 ASIN2026 3000
Digital Twins of Advanced Materials Processing 2000
Polymorphism and polytypism in crystals 1000
Signals, Systems, and Signal Processing 610
Discrete-Time Signals and Systems 610
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 纳米技术 有机化学 物理 生物化学 化学工程 计算机科学 复合材料 内科学 催化作用 光电子学 物理化学 电极 冶金 遗传学 细胞生物学
热门帖子
关注 科研通微信公众号,转发送积分 6041473
求助须知:如何正确求助?哪些是违规求助? 7782017
关于积分的说明 16234686
捐赠科研通 5187524
什么是DOI,文献DOI怎么找? 2775800
邀请新用户注册赠送积分活动 1758937
关于科研通互助平台的介绍 1642416