AbstractsTransportation

Les problèmes de tournées de véhicules cumulatives avec capacité (CCVRP) sont étudiés dans cette thèse, où la minimisation de la somme des temps d'arrivée reflète mieux les objectifs stratégiques de la logistique humanitaire.Dans le problème de multiples tournées d’un véhicule cumulatif avec capacité (mt-CCSVRP), un seul véhicule est disponible et il peut effectuer plusieurs voyages. Un algorithme du plus court chemin avec contrainte de ressources est proposé pour résoudre ce problème, dans lequel les tournées deviennent des nœuds et les sites sont des ressources. Le réseau est orienté et acyclique en raison des propriétés particulières du mt-CCSVRP.Le problème de multiples tournées de véhicules cumulatives avec capacité (mt-CCVRP) est introduit, où plusieurs véhicules peuvent effectuer multiples voyages. Quatre programmes linéaires en nombre entiers (PLNE) sont proposés pour résoudre le CCVRP. Un PLNE pour le mt-CCVRP est proposé ainsi que trois métaheuristiques : une recherche locale itéré à démarrages multiples (MS-ILS), un algorithme mémétique avec gestion de la population (MA|PM) et une recherche locale évolutive à démarrages multiples (MS-ELS), qui appellent un algorithme de recherche local à voisinages variables (VND). Une méthode split à deux phases permet MA|PM et MS-ELS d'alterner entre deux espaces de solutions.Le problème de tournées de véhicules cumulatif avec capacité et des livraisons indirectes (CCVRP-ID) permet aux sites non visités si leurs demandes sont fournies par un véhicule auxiliaire. Un PLNE et un MS-ELS sont développés The cumulative capacitated vehicle routing problems (CCVRP) are studied in this thesis, where the minimization of the sum of arrival times better reflects the strategic objectives of humanitarian logistics.In the multitrip cumulative capacitated single-vehicle routing problem (mt-CCSVRP), only one vehicle is available and it can perform multiple trips. An exact resource constrained shortest path algorithm is proposed for this problem, in which trips become nodes and sites are resources. The resulting network is proven to be directed and acyclic due to the special properties of the mt-CCSVRP.The multitrip cumulative capacitated vehicle routing problem (mt-CCVRP) is introduced, where several vehicles can do multiple trips. Four mixed integer linear programs (MILP) are proposed to solve the CCVRP. For the mt-CCVRP a MILP is also given as well as three metaheuristics: a multi-start iterated local search (MS-ILS), a memetic algorithm with population management (MA|PM) and a multi-start evolutionary local search (MS-ELS), which call a variable neighborhood descent algorithm (VND). A two phases split method allows MA|MS and MS-ELS to alternate between two spaces of solutions.The cumulative capacitated vehicle routing problem with indirect deliveries (CCVRP-ID) allows unvisited sites if their demands are provided by an auxiliary vehicle. An MILP and an MS-ELS are developed