A simple greedy algorithm for a class of shuttle transportation problems |
| |
Authors: | Yujun Zheng Chuanqing Xu Jinyun Xue |
| |
Institution: | (1) Institute of Software, Chinese Academy of Sciences, 100080 Beijing, China;(2) Academy of Armored Force Engineering, 100072 Beijing, China;(3) Provincial Key Lab of High-Performance Computing, Jiangxi Normal University, 330023 Nanchang, China |
| |
Abstract: | Greedy algorithms for combinatorial optimization problems are typically direct and efficient, but hard to prove optimality.
The paper presents a special class of transportation problems where a supplier sends goods to a set of customers, returning
to the source after each delivery. We show that these problems with different objective functions share a common structural
property, and therefore a simple but powerful generic greedy algorithm yields optimal solutions for all of them. |
| |
Keywords: | Greedy algorithm Shuttle transportation problems Combinatorial optimization |
本文献已被 SpringerLink 等数据库收录! |
|