A Network Flow Based Heuristic for Bulk Pickup and Delivery Routing

Fisher, Marshall L.; Tang, Baoxing; Zhang Zheng
February 1995
Transportation Science;Feb95, Vol. 29 Issue 1, p45
Academic Journal
We consider a problem in which a fleet of vehicles must be scheduled to pickup and deliver a set of orders in truckload quantities. We describe a new algorithm based on a network flow relaxation which imposes necessary conditions on the flow of empty vehicles from order delivery points to order pickup points. The network flow model provides a lower bound and a nearly feasible solution that can be made feasible with some simple heuristics. Our algorithm is fast and has performed well on a set of more than 430 test problems which include a number of real problems obtained from the Shanghai Truck Transportation Corporation. On real problems and on random problems generated using real pickup and delivery points, the algorithm consistently produces solutions within 1% of optimality.


Related Articles

  • A Sensitivity Analysis of Multicommodity Network Flows. Jarvis, John J.; Martinez, Oscar Mejia // Transportation Science;Nov77, Vol. 11 Issue 4, p299 

    Given the multicommodity flow solution for a current transportation or communication network, planners often require some kind of heuristic measure of the effectiveness of new links which might potentially be added to the network. Exact procedures are usually prohibitive or expensive to use....

  • RISE OF THE VAN.  // Truck & Driver;Nov2004, p7 

    The article cites British government statistics, according to which, use of light vans increased by 5.2 percent. Two-axle rigids, the most common trucks in Great Britain, accounted for 41 percent of all goods vehicle traffic in 2003.

  • Truck freight traffic jumps on West Side. Lamm, Greg // Journal of Business (10756124);6/3/2004, Vol. 19 Issue 12, p19 

    Reports on the increase in the truck freight traffic in western Washington state by more than 140% since 1994, according to the data from Washington State University transportation economists. Increase in the total truck-cargo weight; Forecasted growth of the Greater Seattle-Tacoma area and its...

  • Road to Perdition. Roth, Marcus // E: The Environmental Magazine;Jul/Aug2005, Vol. 16 Issue 4, p20 

    The article reports that fifteen years from now, 28,000 trucks a day, many of them hauling double or triple trailers, may be speeding up and down special truck lanes on Virginia's Interstate 81, belching tons of carbon monoxide into the Shenandoah Valley each year. Proponents of "toll...

  • LETTERS. Strong, Kevin; Jones, Rod; Suffling, Keith; Parry, Glyn; Barnes, J // Truck & Driver;Apr2008, p48 

    Several letters to the editor are presented in response to articles in previous issues of "Truck & Driver," including "Fridge Magnate" in the January 2008 issue, a remark on the presence of traffic officers patrolling up and down the motorway network in Great Britain and an outlook on the...

  • ALGORITHM FOR TRAFFIC CONTROL. Dunne, Michael C.; Potts, Renfrey B. // Operations Research;Nov/Dec64, Vol. 12 Issue 6, p870 

    A linear control algorithm is proposed for the computer operation of a signalized traffic intersection. A theoretical analysis of the algorithm under the assumption of constant vehicular arrival and departure rates shows that the control is stable under unsaturated conditions, and with proper...

  • TROUBLESPOTS TO WATCH FOR IN MAY/JUNE.  // Truck & Driver;Jun2003, p37 

    This article presents a list of the geographical locations which are likely to pose a problem for the overland transportation and trucking industry in Great Britain. 24 hour roadworks with the carriageway closed and a contraflow in the southbound carriageway for bridge strengthening work due to...

  • Cross-Channel traffic up 5% in first quarter.  // Motor Transport;6/1/2006, p1 

    The focuses on the increase in Cross-Channel traffic in the first quarter of 2006 compared with the same period in 2005 in Great Britain. This reflects a more buoyant Eurozone economy, says the Freight Transport Association. The share of accompanied traffic taken by British-registered trucks is...

  • Goods Vehicle Travelling to Europe.  // Logistics & Transport Focus;Apr 2001, Vol. 3 Issue 3, p5 

    Presents the results of a report on the total number of goods vehicles travelling to mainland Europe from Great Britain in the third quarter of 2000. Decrease in the total number of vehicles travelling to mainland Europe; Statistics indicating the total number of foreign-registered powered...


Read the Article


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

Try another library?
Sign out of this library

Other Topics