Skip to Main content Skip to Navigation
Book sections

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

Abstract : 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.
Document type :
Book sections
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02493514
Contributor : Daniel Gavrysiak <>
Submitted on : Thursday, February 27, 2020 - 7:12:40 PM
Last modification on : Friday, February 28, 2020 - 1:31:19 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

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⟩

Share

Metrics

Record views

61