A multi‐commodity, capacitated pickup and delivery problem: The single and two‐vehicle cases

A multi‐commodity, capacitated pickup and delivery problem: The single and two‐vehicle cases

0.00 Avg rating0 Votes
Article ID: iaor20118859
Volume: 215
Issue: 3
Start Page Number: 572
End Page Number: 580
Publication Date: Dec 2011
Journal: European Journal of Operational Research
Authors:
Keywords: programming: dynamic
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.

Reviews

Required fields are marked *. Your email address will not be published.