1334. Vehicle routing problem with backhauls, time windows and stochastic demand
Invited abstract in session ME-19: Vehicle Routing, cluster Combinatorial Optimization.
Monday, 16:15-17:45Room: FENH105
Authors (first author is the speaker)
| 1. | Gustavo Gatica
|
| Facultad de Ingeniería, Universidad Andres Bello | |
| 2. | Daniela Quila
|
| Faculty of Engineering, Universidad Andres Bello | |
| 3. | Daniel Morillo Torres
|
| Department of Civil and Industrial Engineering, Pontificia Universidad Javeriana - Cali | |
| 4. | Rodrigo Linfati
|
| Universidad del Bio-Bio | |
| 5. | jairo Coronado-Hernandez
|
| Universidad de la Costa |
Abstract
A generalization of the vehicle routing problem with backhauls and time windows (VRPBTW) is proposed, with the possible reduction of vehicles and a penalty cost. In addition, it involves a homogeneous vehicle fleet and a single central depot, to enhance certain aspects of the present study. The VRPBTW problem combines temporal and spatial aspects; undoubtedly, this represents a computationally challenging problem. If the variant with uncertain demands is added, it becomes academically interesting; a model is presented to solve the VRPBTW, with time constraints and stochastic demand (SDVRPBTW). Customers are divided into two subsets, delivery and pickup. Each vehicle leaves the depot to deliver commodities to Linehauls customers, but the quantity to be delivered is uncertain. After delivery, commodities are picked up from as many customers as possible (to utilize the vehicle capacity) and returned to the depot. The objective is to minimize the total distance, the number of vehicles to complete the route and the amount of missing demand, due to the variation of demand in each scenario.
The problem without uncertainty, posed in the literature as a deterministic routing problem, has known demands. Naturally, a problem with uncertain demand is compared by taking the previously obtained solution with the model without uncertainty. This solution is evaluated in different scenarios with demand changes, to demonstrate, by taking into account the random component, better solutions can be obtained, compared to not considering the uncertainty in the demand.
Finding a feasible solution for VRPBTW with a fixed number of vehicles is an NP-Hard problem. Applications of SDVRPBTW arise in both the public and private sectors, such as waste collection scheduling.
The problem is addressed by means of a single-stage implementation of a mixed integer linear programming model. Subsequently, different scenarios are generated by simulating the randomness of the problem; random samples are solved using the sample average approximation (SAA) technique, and the candidate solutions are evaluated in a Monte Carlo simulation. The model is implemented with AMPL and solved with CPLEX 12.8.0.0. Its effectiveness is evaluated based on artificial stochastic data adapted from the literature, for small- and medium-sized generated instances (up to 30 nodes).
Keywords
- Stochastic Models
- Combinatorial Optimization
- VRP
Status: accepted
Back to the list of papers