A Joint Vehicle Routing and Speed Optimization Problem

DOI10.1287/IJOC.2018.0810MaRDI QIDQ5137953zbMATH OpenOpenAlexFDO

Authors

Publication date 3 December 2020

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.08508

zbMATH Keywords

branch and priceGreen transportationmixed integer convex optimizationspeed optimizationvehicle routing problem

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: Fuel cost contributes to a significant portion of operating cost in cargo transportation. Though classic routing models usually treat fuel cost as input data, fuel consumption heavily depends on the travel speed, which has led to the study of optimizing speeds over a given fixed route. In this paper, we propose a joint routing and speed optimization problem to minimize the total cost, which includes the fuel consumption cost. The only assumption made on the dependence between the fuel cost and travel speed is that it is a strictly convex differentiable function. This problem is very challenging, with medium-sized instances already difficult for a general mixed-integer convex optimization solver. We propose a novel set partitioning formulation and a branch-cut-and-price algorithm to solve this problem. Our algorithm clearly outperforms the off-the-shelf optimization solver, and is able to solve some benchmark instances to optimality for the first time.

Recommendations

• A multi‐vehicle covering tour problem with speed optimization
• A dynamic vehicle routing problem with time-dependent travel times
• The Simultaneous Origin-Destination Assignment and Vehicle Routing Problem
• Optimal vehicle routing with lower and upper bounds on route durations
• A time-dependent vessel routing problem with speed optimization
• Multi-objective vehicle routing problems
• The Vehicle Routing Problem with Time Constraints
• A Combined Vehicle Routing and Inventory Allocation Problem

Cites work

• A matheuristic approach for the pollution-routing problem
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• A review of recent research on green road freight transportation
• A speed and departure time optimization algorithm for the pollution-routing problem
• A time bucket formulation for the traveling salesman problem with time windows
• An adaptive large neighborhood search heuristic for the pollution-routing problem
• Analysis of an exact algorithm for the vessel speed optimization problem
• Benchmark Suite for Industrial and Tramp Ship Routing and Scheduling Problems
• Branch-and-price: Column generation for solving huge integer programs
• Fundamental properties and pseudo-polynomial-time algorithm for network containership sailing speed optimization
• scientific article; zbMATH DE number 1452994 (Why is no real title available?)
• Improved branch-cut-and-price for capacitated vehicle routing
• New route relaxation and pricing strategies for the vehicle routing problem
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• Reducing fuel emissions by optimizing speed on shipping routes
• Selected Topics in Column Generation
• Shortest Path Problems with Resource Constraints
• Solving the asymmetric travelling salesman problem with time windows by branch-and-cut
• Vehicle Routing

Cited in

(12)

• Development of a fuel consumption optimization model for the capacitated vehicle routing problem
• A time-dependent vessel routing problem with speed optimization
• A concise guide to existing and emerging vehicle routing problem variants
• Optimization of vehicle speed for batches to minimize supply chain cost under uncertain demand
• Analysis of an exact algorithm for the vessel speed optimization problem
• Fuel emissions optimization in vehicle routing problems with time-varying speeds
• A generic model of motor-carrier fuel optimization
• A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints
• A repeated route-then-schedule approach to coordinated vehicle platooning: algorithms, valid inequalities and computation
• Joint vehicle assembly‐routing problems: An integrated modeling and optimization approach
• A branch-cut-and-price algorithm for the time-dependent electric vehicle routing problem with time windows
• Fuel-optimal truck path and speed profile in dynamic conditions: an exact algorithm

Describes a project that uses

Uses Software

• VRP
• CVRPSEP

This page was built for publication: A Joint Vehicle Routing and Speed Optimization Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5137953)