Bounds and Heuristics for Capacitated Routing Problems

启发式 数学 数学优化 布线(电子设计自动化) 集合(抽象数据类型) 欧几里德几何 上下界 车辆路径问题 渐近最优算法 欧几里德距离 计算机科学 计算机网络 数学分析 几何学 程序设计语言
作者
M. Haimovich,A. H. G. Rinnooy Kan
出处
期刊:Mathematics of Operations Research [Institute for Operations Research and the Management Sciences]
卷期号:10 (4): 527-542 被引量:317
标识
DOI:10.1287/moor.10.4.527
摘要

In a capacitated routing problem, the objective is to minimize the total distance travelled by vehicles of limited capacity to serve a set of customers that are located in the Euclidean plane. We develop asymptotically optimal bounds and heuristics for this problem, under the assumption that the capacity of a vehicle is expressed in terms of an upper bound on the number of customers that it can serve. The analysis culminates in an algorithm that, for a given capacity and given ϵ, will find a solution with relative error at most ϵ in time polynomial in the number of customers.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
LEI完成签到,获得积分20
刚刚
刚刚
THM666发布了新的文献求助10
刚刚
铜板还太少的应助被WU采纳,获得10
刚刚
hey完成签到 ,获得积分10
1秒前
DJ发布了新的文献求助10
1秒前
凶狠的雁芙完成签到,获得积分10
1秒前
Vincy完成签到 ,获得积分10
1秒前
美丽的雪珍完成签到,获得积分10
1秒前
gf完成签到,获得积分10
1秒前
Queen完成签到,获得积分10
1秒前
羊羊发布了新的文献求助10
1秒前
1秒前
HouKk完成签到,获得积分20
1秒前
1秒前
zhang完成签到 ,获得积分10
2秒前
2秒前
小马发布了新的文献求助10
3秒前
3秒前
3秒前
fvsjbc完成签到,获得积分10
4秒前
太阳完成签到,获得积分10
4秒前
小马甲的应助被轩逸采纳,获得10
5秒前
和光同尘完成签到,获得积分10
5秒前
黄橙橙完成签到 ,获得积分10
5秒前
黑米粥发布了新的文献求助200
6秒前
6秒前
研友_Lpa2On完成签到,获得积分10
6秒前
ZD发布了新的文献求助10
6秒前
6秒前
gxiaxia发布了新的文献求助10
6秒前
半梦发布了新的文献求助10
6秒前
科研通AI6.2的应助被Tracy采纳,获得10
7秒前
Tammm完成签到,获得积分10
7秒前
null的应助被心系天下采纳,获得10
7秒前
v0id的应助被凤凰院凶真采纳,获得10
7秒前
酷酷酷完成签到,获得积分10
7秒前
orixero的应助被gouerde采纳,获得10
7秒前
8秒前
背后的谷南完成签到,获得积分10
8秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 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小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8152794
求助须知:如何正确求助?哪些是违规求助? 9549444
关于积分的说明 21693226
捐赠科研通 7741107
什么是DOI,文献DOI怎么找? 3425348
关于科研通互助平台的介绍 2550424
邀请新用户注册赠送积分活动 2468928