Combinatorial optimization: theory, formulations and applications
Reformulations and solution methods to the integrated lot sizing and scheduling pr...
The traveling salesman problem: mathematical models and solution methods
Full text | |
Author(s): |
Pedro Henrique Del Bianco Hokama
Total Authors: 1
|
Document type: | Master's Dissertation |
Press: | Campinas, SP. |
Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
Defense date: | 2011-10-14 |
Examining board members: |
Flávio Keidi Miyazawa;
Vinícius Amaral Armentano;
Thiago Alves de Queiroz
|
Advisor: | Flávio Keidi Miyazawa |
Abstract | |
We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem, and the Three- Dimensional Packing Problem With Loading Constraints. In this problem, a vehicle must be loaded at the depot and deliver boxes to the customers. Every customer has a set of boxes that should receive and our goal is to minimize the travel cost of the vehicle. Unloading is done through a single side of the container and items from an unloading customer must not be blocked by items to be delivered later. We propose exact and heuristic branch-and-cut algorithm to find a minimum cost route. Adaptations of algorithms from the literature and a Constraint Programming formulation is presented to find a packing that consider unloading contraints. We performed computational tests on instances randomly generated and compared results with the algorithms adapted from literature. The results were quite satisfactory resolving several instances in reasonable computational time (AU) | |
FAPESP's process: | 09/13270-0 - Capacity Vehicle Routing Problem with Time Windows and Pickup and Delivery of three-dimensional itens |
Grantee: | Pedro Henrique Del Bianco Hokama |
Support Opportunities: | Scholarships in Brazil - Master |