6533b7dcfe1ef96bd1273579

RESEARCH PRODUCT

Cimo: An efficient 2-phases calculator of multimodal itineraries for real trans-territories based on a dynamic programming

subject

description

In this work we propose an exact solution for calculating multimodal itinerary. This solution is named Cimo (Calculateur d'Itineraires Multimodaux Ordonnes). Cimo is an exact optimal itineraries' calculator wherein itineraries are sorted, multimodal, and trans-territorial. The solution is based on a dynamic programming algorithm "cut", "price" and "share". This solution is multi-objectives and multi-constraints. Several versions of this algorithm are proposed following a methodological approach that enables evaluation of efficiency and complexity's gain : through theoretical calculus and benchmarks. In the first version of realistic problem, we propose a solution with itineraries calculated exhaustively and satisfying all the constraints (version. 1.0), then a solution with incremental display of itineraries, including the optimal, following the in-depth course strategy and a smart sorted list of stations and the best itinerary previously calculated (version 1.2), another one's with the calculation of the best solution by implementing the cut on a subset of objectives, as well as the impossibility that a itinerary passes 2 times in the same station (version 2.0). One of the original features of Cimo is that it makes a preliminary phase of calculation of optimal itineraries, modulo the combinatorial instantiation of tri-modalities and also the very first satisfying transition schedule. During the second phase, all other objectives are valued following a certain hierarchy. The second novelty is that Cimo produces the best solution and it is speed-up by a smart sorted list of accessible stations from a reference station according to the degree of correspondence as well as proximity to the target station (version 3.0).