A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints
From MaRDI portal
Publication:2664428
Abstract: We consider a vehicle routing problem which seeks to minimize cost subject to time window and synchronization constraints. In this problem, the fleet of vehicles is categorized into regular and special vehicles. Some customers require both vehicles' services, whose starting service times at the customer are synchronized. Despite its important real-world application, this problem has rarely been studied in the literature. To solve the problem, we propose a Constraint Programming (CP) model and an Adaptive Large Neighborhood Search (ALNS) in which the design of insertion operators is based on solving linear programming (LP) models to check the insertion feasibility. A number of acceleration techniques is also proposed to significantly reduce the computational time. The computational experiments show that our new CP model finds better solutions than an existing CP-based ANLS, when used on small instances with 25 customers and with a much shorter running time. Our LP-based ALNS dominates the cp-ALNS, in terms of solution quality, when it provides solutions with better objective values, on average, for all instance classes. This demonstrates the advantage of using linear programming instead of constraint programming when dealing with a variant of vehicle routing problems with relatively tight constraints, which is often considered to be more favorable for CP-based methods.
Recommendations
- Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints
- Linear formulations for the vehicle routing problem with synchronization constraints
- An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits
- Combined vehicle routing and scheduling with temporal precedence and synchronization constraints
- Heuristic solutions for the vehicle routing problem with time windows and synchronized visits
Cites work
- A general heuristic for vehicle routing problems
- Adaptive large neighborhood search for the vehicle routing problem with synchronization constraints at the delivery location
- Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
- An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits
- An exact constraint logic programming algorithm for the traveling salesman problem with time windows
- Column generation for vehicle routing problems with multiple synchronization constraints
- Combined vehicle routing and scheduling with temporal precedence and synchronization constraints
- Constraint programming for LNG ship scheduling and inventory management
- Heuristic solutions for the vehicle routing problem with time windows and synchronized visits
- scientific article; zbMATH DE number 1082108 (Why is no real title available?)
- Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 6th international conference, CPAIOR 2009, Pittsburgh, PA, USA, May 27--31, 2009. Proceedings
- Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints
- Solving routing problems with pairwise synchronization constraints
- The home care crew scheduling problem: preference-based visit clustering and temporal dependencies
- The Synchronized Dynamic Vehicle Dispatching Problem
- The vehicle routing problem with time windows and temporal dependencies
- Two Evolutionary Metaheuristics For The Vehicle Routing Problem With Time Windows
Cited in
(18)- An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits
- Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints
- The line-haul feeder vehicle routing problem: mathematical model formulation and heuristic approaches
- Linear formulations for the vehicle routing problem with synchronization constraints
- Column generation for vehicle routing problems with multiple synchronization constraints
- A survey of adaptive large neighborhood search algorithms and applications
- An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization
- Branch-and-price-and-cut for the manpower routing problem with synchronization constraints
- A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions
- Optimising the flight turnaround schedules: an improved sliding time windows approach based on MILP and CP models
- Adaptive large neighborhood search for the vehicle routing problem with synchronization constraints at the delivery location
- Flexible vehicle scheduling with precedence constraints for tourists
- Matheuristic for synchronized vehicle routing problem with multiple constraints and variable service time: managing a fleet of sprayers and a tender tanker
- Synchronisation in vehicle routing: classification schema, modelling framework and literature review
- The robust vehicle routing problem with synchronization: models and branch-and-cut algorithms
- A selection hyper-heuristic approach to the single airport slot allocation problem
- A multiple asset-type, collaborative vehicle routing problem with proximal servicing of demands
- E-cargo bike route optimization with rider fatigue considerations: a chance-constrained programming approach
This page was built for publication: A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664428)
