AN ALGORITHM FOR THE GENERALIZED VEHICLE ROUTING PROBLEM WITH BACKHAULING

Subrata Mitra ()
Additional contact information
Subrata Mitra: Indian Institute of Management Calcutta, Joka, Diamond Harbour Road, Kolkata – 700 104, India

Asia-Pacific Journal of Operational Research (APJOR), 2005, vol. 22, issue 02, 153-169

Abstract: The Vehicle Routing Problem with Backhauling deals with the supply of finished goods from a depot to a number of delivery points, and picking up returnable items and bringing them back to the depot using a fleet of trucks. Traditionally, the objective of the problem has been to determine the truck routes such that the total number of trucks and/or the total distance traveled/total route cost are minimized. Most of the papers available in the literature in this connection deal with problems where the linehaul (having a demand for finished goods) and backhaul (having items to be returned to the depot) customers are different, and a customer may be visited by at most one truck limiting demand and returns at a location by the capacity of the truck. In this paper, we allow the linehaul and backhaul customers to be the same leading to simultaneous delivery and pickup at a customer location, and also there is no restriction on the quantity demanded at (to be returned from) a customer location. As such a customer may be visited by more than one truck and more than once by the same truck. We developed a Mixed Integer Linear programming (MILP) formulation of the problem and a route construction heuristic. The heuristic averaged 80 ms for 110 problems tested, and in 78 of them the heuristic costs were either equal to the optimal costs or at most equal to the upper bounds on the optimal costs obtained after running the optimization package for 30 min. Optimal solutions were obtained for 28 problems at an average time of 295 ms. The heuristic could match the optimal solutions for 22 of these problems at an average time of 71 ms.

Keywords: Vehicle routing; backhauling; mixed integer programming; heuristic (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595905000522
Access to full text is restricted to subscribers

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:wsi:apjorx:v:22:y:2005:i:02:n:s0217595905000522

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595905000522

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().