An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem

Archetti, Claudia; Speranza, M. Grazia; Savelsbergh, Martin W. P.
February 2008
Transportation Science;Feb2008, Vol. 42 Issue 1, p22
Academic Journal
The split delivery vehicle routing problem is concerned with serving the demand of a set of customers with a fleet of capacitated vehicles at minimum cost. Contrary to what is assumed in the classical vehicle routing problem, a customer can be served by more than one vehicle, if convenient. We present a solution approach that integrates heuristic search with optimization by using an integer program to explore promising parts of the search space identified by a tabu search heuristic. Computational results show that the method improves the solution of the tabu search in all but one instance of a large test set.


Related Articles

  • Improving Transportation Services for the University of the Thai Chamber of Commerce: A Case Study on Solving the Mixed-Fleet Vehicle Routing Problem with Split Deliveries. Suthikarnnarunai, N.; Olinick, E. // AIP Conference Proceedings;1/12/2009, Vol. 1089 Issue 1, p200 

    We present a case study on the application of techniques for solving the Vehicle Routing Problem (VRP) to improve the transportation service provided by the University of The Thai Chamber of Commerce to its staff. The problem is modeled as VRP with time windows, split deliveries, and a mixed...

  • Pickup and Delivery with Split Loads. Nowak, Maciek; Ergun, Öziem; White, III, Chelsea C. // Transportation Science;Feb2008, Vol. 42 Issue 1, p32 

    Splitting loads such that the delivery of certain loads is completed in multiple trips rather than one trip results in opportunities for a reduction in cost and the number of vehicles used. Several studies have shown the benefit of split deliveries for the vehicle routing problem, in which a...

  • OPTIMAL FLEET SIZE, DELIVERY ROUTES, AND WORKFORCE ASSIGNMENTS FOR THE VEHICLE ROUTING PROBLEM WITH MANUAL MATERIALS HANDLING. Boonprasurt, Prachya; Nanthavanij, Suebsak // International Journal of Industrial Engineering;2012, Vol. 19 Issue 6, p252 

    The vehicle routing problem with manual materials handling (VRPMMH) is introduced. At customer locations, delivery workers must manually unload goods from the vehicle and take them to the stockroom. The delivery activities require workers to expend certain amounts of physical energy. In this...

  • Meta Heuristic Algorithms for Vehicle Routing Problem with Stochastic Demands. Shanmugam, Geetha; Ganesan, Poonthalir; Vanathi, P. T. // Journal of Computer Science;2011, Vol. 7 Issue 4, p533 

    Problem statement: The shipment of goods from manufacturer to the consumer is a focal point of distribution logistics. In reality, the demand of consumers is not known a priori. This kind of distribution is dealt by Stochastic Vehicle Routing Problem (SVRP) which is a NP-hard problem. In this...

  • Hubbing and routing in postal delivery systems. Çetiner, Selim; Sepil, Canan; Süral, Haldun // Annals of Operations Research;Dec2010, Vol. 181 Issue 1, p109 

    We consider the combined hubbing and routing problem in postal delivery systems and develop an iterative two-stage solution procedure for the problem. In the first stage, hub locations are determined and postal offices are multiply allocated to the hubs. The second stage gives the routes in hub...

  • Around Africa with a fridge.  // Truck & Driver;Jun2008, p18 

    The article describes the transport of a 50-meter-long, 40-tonne cold box from England to Zambia. The giant cooler traveled by ship to Walvis Bay in Namibia. It was then attached to two 10-axle Goldhofer heavy-duty trailer modules hauled by Mercedes Actros Titan tractors and took the 2,400...

  • New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem. Baldacci, Roberto; Mingozzi, Aristide; Roberti, Roberto // Operations Research;Sep2011, Vol. 59 Issue 5, p1269 

    In this paper, we describe an effective exact method for solving both the capacitated vehicle routing problem (CVRP) and the vehicle routing problem with time windows (VRPTW) that improves the method proposed by Baldacci et al. [Baldacci, R., N. Christofides, A. Mingozzi. 2008. An exact...

  • A Heuristic Based on Integer Programming for the Vehicle Routing Problem with Backhauls. Yalcin, Gulcin Dinc; Erginel, Nihal // Proceedings of the International Conference on Industrial Engine;2012, p1350 

    Vehicle Routing Problem with Backhauls (VRPB) is an extension of vehicle routing problem. In this problem, customers are divided into two sets as linehaul and backhaul customers. All goods are delivered to linehaul customers before goods are brought from backhaul customers. In this study, a...

  • Feasibility of the Pickup and Delivery Problem with Fixed Partial Routes: A Complexity Analysis. Berbeglia, Gerardo; Pesant, Gilles; Rousseau, Louis-Martin // Transportation Science;Aug2012, Vol. 46 Issue 3, p359 

    In the pickup and delivery problem (PDP) a fleet of vehicles must serve customers' requests, which consist of transporting objects from their origins to their destinations. We introduce the PDP with fixed partial routes (PDP-FPR), in which some partial routes are given, and the problem consists...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics