Computing at Glasgow University
Paper ID: 6476

On the Reformulation of Vehicle Routing Problems and Scheduling Problems
Beck,J.C. Prosser,P. Selensky,E.

Publication Type: Conference Proceedings
Appeared in: Proceedings of SARA 2002, Symposium on Abstraction, Reformulation and Approximation
Page Numbers : 282 - 289
Publisher: LNCS, Springer
Year: 2002

Note: LNCS 2371


We can reformulate a vehicle routing problem (VRP) as an open shop scheduling problem (SSP) by representing visits as activities, vehicles as resources on the factory floor, and travel as set up costs between activities. In this paper we present two reformulations: from VRP to open shop, and the inverse, from SSP to VRP. Not surprisingly, VRP technology performs poorly on reformulated SSP's, as does scheduling technology on reformulated VRP's. We present a pre-processing transformation that ``compresses'' the VRP, transforming an element of travel into the duration of the visits. The compressed VRP's are then reformulated as scheduling problem, to determine if it is primarily distance in the VRP that causes scheduling technology to degrade on the reformulated problem. This is a step towards understanding the features of a problem that make it more amenable to one technology rather than another.

PDF Bibtex entry Endnote XML