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

2018-02-01
Farham, Mohammad Saleh
Süral, Haldun
İyigün, Cem
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.
COMPUTERS & OPERATIONS RESEARCH

Suggestions

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.