Heuristic solution techniques for the split delivery vehicle routing problem

作者
Renate Popelka
链接
摘要

Die Diplomarbeit befasst sich mit dem Split Delivery Vehicle Routing Problem (SDVRP). Im Gegensatz zum klassischen Vehicle Routing Problem (VRP) kann es vorkommen, dass ein Kunde von mehr als einem Fahrzeug beliefert wird. Zwei heuristische Losungsverfahren fur das SDVRP werden genauer vorgestellt, namlich der Algorithmus von Dror und Trudeau und der Savings Algorithmus von Clarke und Wright, welcher auf eine Version mit Teillieferungen erweitert wurde. Beide Heuristiken wurden mit C++ implementiert und die Effizienz der Algorithmen wurde anhand von 42 Testinstanzen untersucht. Diese Instanzen unterscheiden sich in der Anzahl der Kunden (50-199 Kunden) und der Hohe der Nachfragemengen. Die Losungen der Algorithmen fur das SDVRP werden mit den Losungen eines VRP verglichen, um zu zeigen, dass die Einfuhrung von Teillieferungen zu erheblichen Ersparnissen in der zuruckgelegten Distanz und der Anzahl an benotigten Fahrzeugen fuhren kann. Die Untersuchung der Losungen der umgesetzten Heuristiken fur das SDVRP macht deutlich, dass beide Heuristiken im Durchschnitt gleichwertig sind. Lediglich die Laufzeiten des Savings Algorithmus mit Teillieferungen sind viel hoher als die des Algorithmus von Dror und Trudeau. Im Allgemeinen kann gesagt werden, dass die umgesetzten Heuristiken gute Losungen bringen. Allerdings gibt es bereits Algorithmen fur das SDVRP, die besser sind. Ein Vergleich mit den zur Verfugung gestellten Losungen des Tabu Search fur das SDVRP von Archetti, Hertz und Speranza zeigt, dass ihre Ergebnisse durchschnittlich um circa 2 % besser sind als die Ergebnisse der Algorithmen, die in der Diplomarbeit prasentiert werden.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
一斤完成签到 ,获得积分10
1秒前
1秒前
游子轩完成签到,获得积分10
1秒前
wcy完成签到,获得积分10
1秒前
1秒前
小油菜完成签到 ,获得积分10
1秒前
年轻哈密瓜完成签到,获得积分10
1秒前
小周完成签到,获得积分20
1秒前
星空完成签到,获得积分10
1秒前
科研小辣鸡完成签到,获得积分10
1秒前
duxing发布了新的文献求助10
1秒前
h11的应助被zhiruiwang采纳,获得10
2秒前
初晴完成签到 ,获得积分10
2秒前
戒骄戒躁完成签到,获得积分20
2秒前
于骨头完成签到 ,获得积分10
3秒前
4秒前
4秒前
4秒前
完美世界的应助被Rony采纳,获得10
4秒前
Crazy_Runner发布了新的文献求助10
4秒前
嘉的科研完成签到,获得积分10
4秒前
5秒前
66hbb完成签到,获得积分10
5秒前
蜂蜜柚子完成签到,获得积分10
5秒前
呜呜呜啦完成签到,获得积分10
5秒前
5秒前
Lsy完成签到,获得积分10
5秒前
王某某完成签到,获得积分10
5秒前
夏目完成签到 ,获得积分10
5秒前
曾经安萱完成签到,获得积分10
5秒前
炫舞精灵完成签到,获得积分10
5秒前
FD完成签到,获得积分10
6秒前
霸气导师完成签到,获得积分10
6秒前
自由的山芙完成签到,获得积分10
6秒前
6秒前
碧蓝的柠檬完成签到,获得积分10
7秒前
zhvjdb完成签到,获得积分10
7秒前
妮妮发布了新的文献求助10
7秒前
LiuHX完成签到,获得积分10
7秒前
77完成签到,获得积分10
7秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 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