A multi-commodity, capacitated pickup and delivery problem: The single and two-vehicle cases |
| |
Authors: | Harilaos N Psaraftis |
| |
Institution: | Laboratory for Maritime Transport, National Technical University of Athens, Greece |
| |
Abstract: | We explore dynamic programming solutions for a multi-commodity, capacitated pickup and delivery problem. Cargo flows are given by an origin/destination matrix which is not necessarily symmetric. This problem is a generalization of several known pickup and delivery problems, as regards both problem structure and objective function. Solution approaches are developed for the single-vehicle and two-vehicle cases. The fact that for each cargo that goes from a node i to another node j there may be a cargo going in the opposite direction provides the motivation for the two-vehicle case, because one may conceivably consider solutions where no cargoes that travel in opposite directions between node pairs are carried by the same vehicle. Yet, it is shown that such scenarios are generally sub-optimal. As expected, the computational effort of the single vehicle algorithm is exponential in the number of cargoes. For the two-vehicle case, said effort is of an order of magnitude that is not higher than that of the single-vehicle case. Some rudimentary examples are presented or both the single-vehicle and two-vehicle cases so as to better illustrate the method. |
| |
Keywords: | Routing Scheduling Pickup and delivery |
本文献已被 ScienceDirect 等数据库收录! |
|