Complexity and Reducibility of the Skip Delivery Problem

Archetti, C.; Mansini, R.; Speranza, M. G.
May 2005
Transportation Science;May2005, Vol. 39 Issue 2, p182
Academic Journal
In the skip delivery problem (SDP), a fleet of vehicles must deliver skips to a set of customers. Each vehicle has a maximum capacity of two skips, and has to start and end its tour at a central depot. The demand of each customer can be greater than the capacity of the vehicles. The objective is to minimize the cost of the total distance traveled by the vehicles to serve all the customers. We show that the SDP is solvable in polynomial time, while its generalization to the case where all vehicles have a capacity greater than two, known as the split delivery vehicle routing problem (SDVRP), is shown to be NP-hard, even under restricted conditions on the costs. We also show that, if the costs are symmetrical and satisfy the triangle inequality, the SDP is reducible in polynomial time to a problem of possibly smaller size, where each customer has unitary demand. This property allows a remarkable simplification of the problem.


Related Articles

  • Effectiveness of an improved road safety policy in Ethiopia: an interrupted time series study. Abegaz, Teferi; Berhane, Yemane; Worku, Alemayehu; Assrat, Abebe // BMC Public Health;2014, Vol. 14 Issue 1, p1580 

    Background In recent years, there has been an increasing interest in implementing road safety policy by different low income countries. However; the evidence is scarce on its success in the reduction of crashes, injuries and deaths. This study was conducted to assess whether road crashes,...

  • Multiple choices.  // Motor Transport;11/27/2008, p19 

    The article offers information on the drawbacks of weight saving related to commercial vehicles. For building materials supplier Wolseley UK, the challenge is providing vehicles that can deliver a wide range of goods from locally-based depots to its customers. Fleet engineer Roy McCrudden...

  • Multi-modal hubs battle Nimbyism. Walton, Christopher // Commercial Motor;8/26/2010, Vol. 213 Issue 5396, p18 

    The article investigates the reason behind the cancellation of plans to build the rail and road freight hub, Kent International Gateway (KIG), in Kent, England. It states that the local residents of Bearsted, a nearby village, were not pleased with the proposals and mounted a campaign to oppose...

  • TECHNICAL NEWS.  // Motor Transport;4/29/2004, p8 

    Presents news briefs on the motor vehicle industry in Great Britain as of April 29, 2004. Purchase of trucks with automated transmission by Gulliver's Truck Hire; Launch of service for repair of bodies at customers' depots of Aire Truck Bodies; Acquisition of a low-loader by 777 Demolition...

  • Downton makes moves in Cheshire.  // Commercial Motor;7/22/2010, Vol. 213 Issue 5391, p23 

    The article offers news briefs related to the transport industry in Great Britain. CM Downton is seeking permission to open a depot for its vehicles and trailers in Runcorn in Cheshire, England. Elddis Transport is seeking permission to base its vehicles and trailers on the Stanley Industrial...

  • MAN NEWBIES:.  // Motor Transport;2/12/2009, p3 

    The article reports that Owens Road Services has taken delivery of eight MAN TGX 26.440BLS 6x2 units with a further 12 to come. The vehicles have been acquired through MAN Financial Services, representing a spend of £1m. The MANs will run double-shifts between Owens' Bridgend depot and its...

  • 100%. Cannon, Bill // Motor Age;Aug2005, Vol. 124 Issue 8, p4 

    Expresses an opinion on the need for automotive service technicians to master all of the vehicle models that they work on. Views on the uselessness of product manuals; Importance of technicians to customers.

  • Aggregate goes for Cambridge site.  // Commercial Motor;8/26/2010, Vol. 213 Issue 5396, p23 

    The article reports that building materials supplier Aggregate Industries Inc. is seeking authorization to base its vehicles for a new operating center in Cambridge, England.

  • Tebay depot to open.  // Motor Transport;9/25/2003, p3 

    Provides information on the plan of contract distribution firm Trans Haul to open a depot at Tebay, Cumbria in England. Location of the site; Service offerings of the depot; Appointment of Martin Richter as manager of the Tebay depot.


Read the Article


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

Try another library?
Sign out of this library

Other Topics