Fleet Size and Mix Pickup and Delivery Problem with Time Windows: A Novel Approach by Column Generation Algorithm - Université de technologie de Troyes Accéder directement au contenu
Chapitre D'ouvrage Année : 2018

Fleet Size and Mix Pickup and Delivery Problem with Time Windows: A Novel Approach by Column Generation Algorithm

Résumé

In this paper, a new efficient column generation algorithm is proposed to tackle the Fleet Size and Mix Pick-up and Delivery Problem with Time Windows (FSMPDPTW). This work is motivated by fleet sizing for a daily route planning arising at a Hospital centre. Indeed, a fleet of heterogeneous rented vehicles is used every day to pick up goods to the locations and to deliver it to other locations. The heterogeneous aspect of the fleet is in term of fixed cost, capacity, and fuel consumption. The objective function is the minimization of the total fixed cost of vehicles used and the total routing cost. The problem is modelled as a set partitioning problem, and an efficient column-generation algorithm is used to solve it. In the resolution, the pricing problem is decomposed in sub-problems, such that each vehicle type has its own sub-pricing problem. A mixed integer linear program, a powerful labelling algorithm and the regret heuristic is provided to solve the pricing sub-problems. Based on Li and Lim’s benchmark (altered Solomon’s benchmark) for demands and from Lui and Shen’s benchmark for vehicles types; a new set of benchmarks is proposed to test the efficiency of the propound algorithm.
Fichier non déposé

Dates et versions

hal-02493514 , version 1 (27-02-2020)

Identifiants

Citer

Moïse Noumbissi Tchoupo, Alice Yalaoui, Lionel Amodeo, Farouk Yalaoui, Pauline Flori. Fleet Size and Mix Pickup and Delivery Problem with Time Windows: A Novel Approach by Column Generation Algorithm. New Trends in Emerging Complex Real Life Problems, 1, pp.387-398, 2018, AIRO Springer Series, 978-3-030-00473-6. ⟨10.1007/978-3-030-00473-6_41⟩. ⟨hal-02493514⟩

Collections

CNRS UTT LOSI
58 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More