Skip to main content
European Commission logo

Combinatorial Optimization Problems in Transportation Systems

Complete with results
Geo-spatial type
STRIA Roadmaps
Network and traffic management systems (NTM)
Transport policies
Societal/Economic issues


Background & Policy context

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.


Parent Programmes
Institution Type
Public institution
Type of funding
Public (national/regional/local)
Funding Source
Scientific Grant Agency


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).


Lead Organisation
EU Contribution
Partner Organisations
EU Contribution


Contribute! Submit your project

Do you wish to submit a project or a programme? Head over to the Contribute page, login and follow the process!