Fleet Size and Mix Pickup and Delivery Problem with Time Windows: A Novel Approach by Column Generation Algorithm - Archive ouverte HAL Access content directly
Book Sections Year : 2018

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

(1) , (1) , (1) , (1) , (2)
1
2

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.
Not file

Dates and versions

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

Identifiers

Cite

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
49 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More