A column generation approach for the location-routing problem with time windows. (February 2018)

• Record Type: Journal Article
• Authors: Farham, Mohammad Saleh; Süral, Haldun; Iyigun, Cem
• Is Part Of: Computers & operations research. Volume 90(2018)
• Page Start: 249
• Page End: 263
• Publication Date: 2018-02
• Subjects: Location-routing problem -- Time windows -- Column generation -- Branch-and-price; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.09.010
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A branch-and-price algorithm is proposed to solve the LRPTW optimally. Acceleration techniques are applied to enhance the column generation procedure. To solve the problem more efficiently, a heuristic approach is introduced. A large set of LRPTW instances with different characteristics is solved. The effect of providing upper-bounds on the performance of the exact algorithm is studied. Abstract: The location-routing problem with time windows consists of opening a subset of depots, assigning customers to depots, and determining routes within allowable times such that the sum of depot opening, vehicle usage, and traveling costs is minimized. Customers have to be visited only once during their time windows and depot capacities and load limits of vehicles cannot be violated. In order to find the exact solution to the problem, we propose a branch-and-price algorithm based on set-partitioning approach. The pricing problem is solved using dynamic programming. We introduce several strategies to improve the lower and upper bounds as well as acceleration techniques to generate improving columns more rapidly. Computational results show the higher performance of the proposed method on a set of small and medium size instances in the literature and demonstrate its efficiency in solving generated large size instances.