Overview
The costs generated by transportation systems represent a significant portion of total logistic cost. Optimal exploitation of transportation capacities is the key task for sustainability of logistic systems. Various problems arising in the practise can be formulated as combinatorial optimization problems. Various models are built with the tools of graph theory and integer linear programming and research is focused to appropriate solution methods of combinatorial problems. Several problems formulated theoretically are analogous to practical problems of transportation.
The project aims at solving the optimization problems derived from arc routing and vehicle routing problems. The handled problems belong to the NP-hard class thus metaheuristic methods such as tabu search or evolutionary algorithms shall be applied to solve problems of a real size. The proposed methods will be tested on available benchmark instances or other data sets generated randomly. The main target of the project is to treat newly formulated problems, and propose and test effective metaheuristics.
Funding
Results
The project deals with a bi-objective multiple traveling salesman problem with profits (BOMTSPP), generalizing the classical TSP with profits (TSPP). The TSPP is in fact a generic name for TSP problems taking into account the length of the tour and profits collected at customers. However, all these problems are not really bi-objective: the two criteria are aggregated into a single objective or one of them is replaced by a constraint. Our BOMTSPP aims at building m cycles covering a subset of potential customers so that the total collected profit is maximized and the overall traveling distance is minimized. This new problem generalizes the TSPP in two directions: a true bi-objective treatment and the construction of multiple tours. The proposed solution method is an effective evolutionary algorithm, reinforced by a post-optimization procedure based on path-relinking (PR).