Solving a Practical Pickup and Delivery Problem

列生成 皮卡 车辆路径问题 解算器 数学优化 卡车 计算机科学 线性规划松弛 集合(抽象数据类型) 线性规划 布线(电子设计自动化) 整数规划 工程类 数学 计算机网络 汽车工程 人工智能 图像(数学) 程序设计语言
作者
Hang Xu,Zhi-Long Chen,S. Rajagopal,Sundar Arunapuram
出处
期刊:Transportation Science [Institute for Operations Research and the Management Sciences]
卷期号:37 (3): 347-364 被引量:229
标识
DOI:10.1287/trsc.37.3.347.16044
摘要

We consider a pickup and delivery vehicle routing problem commonly encountered in real-world logistics operations. The problem involves a set of practical complications that have received little attention in the vehicle routing literature. In this problem, there are multiple carriers and multiple vehicle types available to cover a set of pickup and delivery orders, each of which has multiple pickup time windows and multiple delivery time windows. Orders and carrier/vehicle types must satisfy a set of compatibility constraints that specify which orders cannot be covered by which carrier/vehicle types and which orders cannot be shipped together. Order loading and unloading sequence must satisfy the nested precedence constraint that requires that an order cannot be unloaded until all the orders loaded into the truck later than this order are unloaded. Each vehicle trip must satisfy the driver's work rules prescribed by the Department of Transportation which specify legal working hours of a driver. The cost of a trip is determined by several factors including a fixed charge, total mileage, total waiting time, and total layover time of the driver. We propose column generation based solution approaches to this complex problem. The problem is formulated as a set partitioning type formulation containing an exponential number of columns. We apply the standard column generation procedure to solve the linear relaxation of this set partitioning type formulation in which the resulting master problem is a linear program and solved very efficiently by an LP solver, while the resulting subproblems are computationally intractable and solved by fast heuristics. An integer solution is obtained by using an IP solver to solve a restricted version of the original set partitioning type formulation that only contains the columns generated in solving the linear relaxation. The approaches are evaluated based on lower bounds obtained by solving the linear relaxation to optimality by using an exact dynamic programming algorithm to solve the subproblems exactly. It is shown that the approaches are capable of generating near-optimal solutions quickly for randomly generated instances with up to 200 orders. For larger randomly generated instances with up to 500 orders, it is shown that computational times required by these approaches are acceptable.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
顾矜的应助被super chan采纳,获得10
刚刚
俭朴的寇完成签到,获得积分10
刚刚
刚刚
Wang发布了新的文献求助10
刚刚
珂珂完成签到,获得积分10
1秒前
1秒前
1秒前
情怀的应助被花开的石头采纳,获得20
1秒前
2秒前
2秒前
惠的厚度完成签到,获得积分20
2秒前
锅锅发布了新的文献求助10
2秒前
热心市民小红花的应助被1122SS采纳,获得10
2秒前
墨白发布了新的文献求助10
2秒前
合适的芸遥完成签到,获得积分10
3秒前
康荣濠完成签到,获得积分10
3秒前
勤恳化蛹完成签到 ,获得积分10
4秒前
远远完成签到,获得积分10
4秒前
小二郎的应助被飞鸿影下采纳,获得10
4秒前
binbin的应助被果果123采纳,获得10
4秒前
Whisper完成签到 ,获得积分10
4秒前
5秒前
Hyper完成签到,获得积分10
5秒前
5秒前
5秒前
6秒前
王小白完成签到 ,获得积分10
6秒前
Pan完成签到,获得积分10
6秒前
7秒前
zzwwill完成签到,获得积分10
7秒前
8秒前
Kiki发布了新的文献求助10
8秒前
悠闲的自然完成签到 ,获得积分10
8秒前
恐惧完成签到,获得积分10
9秒前
张嘉仪完成签到,获得积分10
9秒前
9秒前
哈哈哈完成签到,获得积分10
9秒前
任性的牛排完成签到,获得积分10
10秒前
爱听歌安彤完成签到,获得积分10
10秒前
10秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1500
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology)求助 1000
Encyclopedia of Modern Artificial Intelligence 1000
John McDowells Bildungstheorie 800
Analyses de reconnaissances de dettes passées devant les échevins d'Ypres (1249-1291) 600
Synthesis, Application and Future Perspectives of Smart Nano-materials - Part 1 400
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8153492
求助须知:如何正确求助?哪些是违规求助? 9550166
关于积分的说明 21696892
捐赠科研通 7742051
什么是DOI,文献DOI怎么找? 3425502
关于科研通互助平台的介绍 2550620
邀请新用户注册赠送积分活动 2469156