车辆路径问题
贪婪算法
计算机科学
数学优化
卡车
皮卡
布线(电子设计自动化)
质量(理念)
算法
班级(哲学)
贪婪随机自适应搜索过程
光学(聚焦)
数学
人工智能
物理
计算机网络
哲学
认识论
图像(数学)
热力学
光学
作者
Marc Goetschalckx,Charlotte Jacobs‐Blecha
标识
DOI:10.1016/0377-2217(89)90057-x
摘要
The Vehicle Routing Problem with Backhauls is a pickup/delivery problem where on each route all deliveries must be made before any pickups. A two-phased solution methodology is proposed. In the first phase, a high quality initial feasible solution is generated based on spacefilling curves. In the second phase, this solution is improved based on optimization of the subproblems identified in a mathematical model of the problem. An extensive computational analysis of several initial solution algorithms is presented, which identifies the tradeoffs between solution quality and computational requirements. The class of greedy algorithms is capacity oriented, while K-median algorithms focus on distance. It is concluded that the greedy and K-median algorithms generate equivalent tour lengths, but that the greedy procedure reduces the required number of trucks and increases the truck utilization. The effect of exchange improvement procedures as well as optimal procedures on solution quality and run time is demonstrated. Comparisons with the Clark—Wright method adapted to backhauls are also given.
科研通智能强力驱动
Strongly Powered by AbleSci AI