Linehaul- Backhaul

Abstract

The Vehicle Routing Problem with Backhauls (VRPB) is an extension of the classical Vehicle Routing Problem (VRP) that includes both a set of customers to whom products are to be delivered, and a set of vendors whose goods need to be transported back to the distribution center. In addition, on each route all deliveries have to be made before any goods can be picked up to avoid rearranging the loads on the vehicle. The primary objective of this paper is to present a new heuristic, called LHBH, for the VRPB. The LHBH heuristic is based on the Generalized Assignment Problem (GAP), and introduces new effective methods for generating an initial solution and for locating the individual routes. Results of a computational study, comparing the LHBH algorithm with other heuristics and a lower bound, show the LHBH heuristic to be a practical and effective solution approach for realistically sized VRPB problems.

Software and Test Data

Click here to view a sample screen from the LINEBACK program and more detailed view of a linehaul-backhaul route. You can also download the beta version of the User's Manual of Lineback, Version 4.0, in Adobe Acrobat PDF format.

You can download a Lineback viewer program running under WIN32, any 32 bit version of Microsoft Windows (Windows NT, Win32s extensions to 16 bit Windows 3.1, or Windows 95 or Windows 98. Click on Scienmfc.dll to download a dynamic link library required by this program which should be placed in the directory for 32 bit DLLs on your system. Click on Lhbhcase.zip to download a ZIP file archive with a number of test case data and solution routes, labeled A1 to O6. Click on Lhbhcase.txt to download an ASCII text file with just the test case data and the length of the routes.

References

Goetschalckx, M. and C. Jacobs-Blecha (1989), "The Vehicle Routing Problem With Backhauls," European Journal of Operational Research, Vol. 42, pp. 39-51.

Goetschalckx, M. and Jacobs-Blecha, C. "Linehaul-Backhaul: Solutions with Spacefilling Curves". Published in Progress in Material Handling and Logistics, Volume I, J. A. White and I. W. Pence (Eds.), Springer Verlag Publishing Co. 1989. Pages 303-346.

Goetschalckx, M. and Jacobs-Blecha, C., "The Vehicle Routing Problem with Backhauls: An Effective Heuristic Based on the Generalized Assignment Problem with Ring Metric Norm," Material Handling Research Center Technical Report TR-88-13.

Goetschalckx, M. and Jacobs-Blecha, C., "The Vehicle Routing Problem with Backhauls: An Optimization Based Approach." Proceedings of the 2nd Industrial Engineering Research Conference, May 26-27, 1993, Los Angeles, California, pp. 504-509.

Back to the start of Linehaul-Backhaul

Back to Research

Back to Logistics Software

Back to Marc Goetschalckx' Home Page