EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2256. On the Chinese Postman Problem With Load-Dependent Costs
Invited abstract in session TB-64: Arc Routing, stream VeRoLog - Vehicle Routing and Logistics.
Tuesday, 10:30-12:00Room: S16 (building: 101)
Authors (first author is the speaker)
| 1. | Paula Segura Martínez
|
| Universitat Politècnica de València | |
| 2. | Isaac Plana
|
| Matemáticas para la Economía y la Empresa, University of Valencia | |
| 3. | Jose Maria Sanchis
|
| Departamento de Matematica Aplicada, Universidad Politecnica de Valencia |
Abstract
The Chinese Postman Problem (CPP) is a classical arc routing problem whose objective is to find a minimum cost tour on a connected undirected graph G that traverses each edge of G at least once. An extension of this problem introduced in the literature is the Chinese Postman Problem with load-dependent costs (CPP-LC), in which the cost of traversing an edge depends on its length and also on the weight of the vehicle at the moment the edge is traversed. This is motivated by the intention of reducing pollution in transportation, since the level of emissions from a vehicle is influenced by factors beyond the distance traveled, such as its load. Two mathematical programming formulations and two metaheuristic algorithms have been proposed in the literature for the CPP-LC solution. We present in this work a new mixed-integer linear programming formulation for the CPP-LC, and propose some valid inequalities to reinforce it. We also develop a study of the incompatibilities of a subset of variables from the formulation and describe all the cliques of the underlying intersection graph, categorizing them into five families of inequalities that are valid for the problem. We design a branch-and-cut algorithm for the CPP-LC solution based on this formulation that incorporates the separation of all the valid inequalities proposed. Some computational results obtained with our new exact procedure are presented and compared with those provided in the literature.
Keywords
- Transportation
- Programming, Mixed-Integer
- Branch and Cut
Status: accepted
Back to the list of papers