A column generation approach for the location-routing problem with time windows

Date

2018-02-01

Author

Farham, Mohammad Saleh
Süral, Haldun
İyigün, Cem

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

257
views

0
downloads

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.

Subject Keywords

Location-routing problem, Time windows, Column generation, Branch-and-price

URI

https://hdl.handle.net/11511/49267

Journal

COMPUTERS & OPERATIONS RESEARCH

DOI

https://doi.org/10.1016/j.cor.2017.09.010

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

A computation-implementation parallelization approach to the vehicle loading and routing problem Çavdar, Bahar; Sokol, Joel (Wiley, 2019-01-01) In this article, we address a version of the capacitated vehicle routing problem where there is a constraint on the total time that can be spent on computing delivery routes and loading the vehicles. This problem, which we call the vehicle loading and routing problem (VLRP), can arise, for example, in the delivery of small, quick-turnaround orders from a warehouse. We propose a computation-implementation parallelization (CIP) approach to solving large VLRP instances, and present computational results showin...
An algorithm for the capacitated vehicle routing problem with time windows Pehlivanoğlu, Osman; Meral, Fatma Sedef; Department of Industrial Engineering (2005) In this thesis the capacitated vehicle routing problem with time windows (VRPTW) is studied, where the objective is to serve a set of geographically dispersed customers with known demands and predefined time windows at the minimum cost. It is hard to find an optimal solution for the VRPTW even if the problem size is small. Therefore, many heuristic methods are developed to obtain near optimal solutions. In this study a local search algorithm is proposed for solving the VRPTW, which consist of route construc...
A genetic algorithm for the uncapacitated single allocation planar hub location problem Damgacioglu, Haluk; DİNLER, DERYA; Özdemirel, Nur Evin; İyigün, Cem (2015-10-01) Given a set of n interacting points in a network, the hub location problem determines location of the hubs (transfer points) and assigns spokes (origin and destination points) to hubs so as to minimize the total transportation cost. In this study, we deal with the uncapacitated single allocation planar hub location problem (PHLP). In this problem, all flow between pairs of spokes goes through hubs, capacities of hubs are infinite, they can be located anywhere on the plane and are fully connected, and each s...
A maximal covering location model in the presence of partial coverage Karasakal, O; Karasakal, Esra (2004-08-01) The maximal covering location problem (MCLP) addresses the issue of locating a predefined number of facilities in order to maximize the number of demand points that can be covered. In a classical sense, a demand point is assumed to be covered completely if located within the critical distance of the facility and not covered at all outside of the critical distance. Since the optimal solution to a MCLP is likely sensitive to the choice of the critical distance, determining a critical distance value when the c...
A Branch-and-Cut Algorithm Using a Strong Formulation and an A Priori Tour-Based Heuristic for an Inventory-Routing Problem Solyali, Oguz; Süral, Haldun (2011-08-01) We address a vendor-managed inventory-routing problem where a supplier ( vendor) receives a given amount of a single product each period and distributes it to multiple retailers over a finite time horizon using a capacitated vehicle. Each retailer faces external dynamic demand and is controlled by a deterministic order-up-to level policy requiring that the supplier raise the retailer's inventory level to a predetermined maximum in each replenishment. The problem is deciding on when and in what sequence to v...

Citation Formats

M. S. Farham, H. Süral, and C. İyigün, “A column generation approach for the location-routing problem with time windows,” COMPUTERS & OPERATIONS RESEARCH, pp. 249–263, 2018, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/49267.