Affordable Access

Publisher Website

A network solution to a general vehicle scheduling problem

Authors
Journal
European Journal of Operational Research
0377-2217
Publisher
Elsevier
Publication Date
Volume
1
Issue
4
Identifiers
DOI: 10.1016/0377-2217(77)90095-9

Abstract

Abstract Dantzig and Fulkerson and later Bellmore et al. have shown that certain vehicle (tanker) scheduling problems can be formulated as minimum cost flow problems on a network. In this paper, the results of Dantzig and Fulkerson are extended to the case where more than one type of vehicle can be used in the determination of an optimal fleet. (In tanker scheduling terminology; how many small, medium and large tankers would form an optical fleet.) It is seen how the problem can be formulated as a modified transportation problem where flow in some arcs is conditioned to there being flow on certain other arcs. These “conditional” transportation problems were solved directly as linear programs and showed the peculiarity of terminating all integer in spite of having a constraint matrix, which does not satisfy the well known sufficient conditions for urimodularity. We discuss the implementation of the model and its empirical results.

There are no comments yet on this publication. Be the first to share your thoughts.