Show simple item record

dc.contributor.authorCook, William
Rich, Jennifer L.
dc.date.accessioned 2018-06-18T17:47:32Z
dc.date.available 2018-06-18T17:47:32Z
dc.date.issued 1999-05
dc.identifier.citation Cook, William and Rich, Jennifer L.. "A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problem with Time Windows." (1999) https://hdl.handle.net/1911/101910.
dc.identifier.urihttps://hdl.handle.net/1911/101910
dc.description.abstract In the vehicle routing problem with time windows a number of identical vehicles must be routed to and from a depot to cover a given set of customers, each of whom has a specified time interval indicating when they are available for service. Each customer also has a known demand, and a vehicle may only serve the customers on a route if the total demand does not exceed the capacity of the vehicle. The most effective solution method proposed to date for this problem is due to Kohl, Desrosiers, Madsen, Solomon, and Soumis. Their algorithm uses a cutting-plane approach followed by a branch-and-bound search with column generation, where the columns of the LP relaxation represent routes of individual vehicles. We describe a new implementation of their method, using Karger's randomized minimum-cut algorithm to generate cutting planes. The standard benchmark in this area is a set of 87 problem instances generated in 1984 by M. Solomon; making use of parallel processing in both the cutting-plane generation and the branch-and-bound search, we solve 80 of these examples, including 10 that were previously unsolved in the literature. Our parallel implementation utilizes the Tread Marks distributed shared memory system.
dc.format.extent 22 pp
dc.title A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problem with Time Windows
dc.type Technical report
dc.date.note May 1999
dc.identifier.digital TR99-04
dc.type.dcmi Text


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record