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

摘要

In this work we propose an exact solution for calculating multimodal itinerary. This solution is named Cimo (Cal-culateur d'Itinéraires Multimodaux Ordonnés). 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).