A decomposition approach to a multi-period vehicle scheduling problem

Jung-Ug Kim and Yeong-Dae Kim

Omega, 1999, vol. 27, issue 4, 421-430

Abstract: We consider a multi-period vehicle scheduling problem (MPVSP) in a transportation system where a fleet of homogeneous vehicles delivers products of a single type from a central depot to multiple (N) retailers. The objective of the MPVSP is to minimize transportation costs for product delivery and inventory holding costs at retailers over the planning horizon. To solve a MPVSP of large size in a reasonable computation time, a two-phase heuristic algorithm is suggested based on a kth shortest path algorithm. In the first phase of the algorithm, the MPVSP is decomposed into N single-retailer problems by ignoring the number of vehicles available. The single-retailer problem is formulated as the shortest path problem and several good delivery schedules are generated for each retailer using the kth shortest path algorithm assuming the exact requirement policy is used in the system. In the exact requirement policy, replenishments occur only when the inventory level is zero. In the second phase, a set of vehicle schedules is selected from those generated in the first phase. The vehicle schedule selection problem is a generalized assignment problem and it is solved by a heuristic based on the kth shortest path algorithm. Computational experiments on randomly generated test problems showed that the suggested algorithm gave near optimal solutions in a reasonable amount of computation time.

Keywords: Transport; Distribution; Vehicle; scheduling; Inventory; control; Integer; programming; Heuristics (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305-0483(98)00067-X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:27:y:1999:i:4:p:421-430

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().