Show simple item record

dc.contributor.advisor Cook, William J.
dc.creatorRich, Jennifer Lynn
dc.date.accessioned 2009-06-04T06:45:47Z
dc.date.available 2009-06-04T06:45:47Z
dc.date.issued 1999
dc.identifier.urihttp://hdl.handle.net/1911/19431
dc.description.abstract This thesis examines three specific routing applications. In the first model, the scheduling of home health care providers from their homes, to a set of patients, and then back to their respective homes, is performed both heuristically and optimally for very small instances. The problem is complicated by the presence of multiple depots, time windows, and the scheduling of lunch breaks. It is shown that the problem can be formulated as a mixed integer programming problem and, in very small instances, solved to optimality with a branch-and-cut procedure. To obtain solutions for larger instances, though, a heuristic is shown to have more success. The second application considers the vehicle routing problem with time windows, or VRPTW. The vehicle routing problem involves finding a set of routes starting and ending at a single depot that together visit a set of customers. In the VRPTW, there is an additional constraint requiring that each customer must be visited within a given time window. The best known solution procedures for solving the VRPTW use a set partitioning model with column generation. Within this framework, we present a new approach for generating valid inequalities, specifically k-path cuts, to improve the linear programming relaxation. Computational results are given for the standard library of test instances. In particular, the results include solutions for ten previously unsolved instances. The final application concerns the less-than-truckload, or LTL, trucking industry. An LTL carrier primarily handles shipments that are significantly smaller than the size of a tractor-trailer. Savings are achieved by consolidating shipments into loads at regional terminals and transporting these loads from terminal to terminal. The strategic load plan determines how to route the flow of consolidated loads from origin terminals to destination terminals cost effectively and allowing for certain service standards. To find good solutions to this problem, we apply a dual-ascent procedure to a related uncapacitated network design problem to obtain computational results for three different companies.
dc.format.extent 162 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectOperations research
Computer science
dc.title A computational study of vehicle routing applications
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation Rich, Jennifer Lynn. "A computational study of vehicle routing applications." (1999) Diss., Rice University. http://hdl.handle.net/1911/19431.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record