EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

10. Two-Commodity Opposite Direction Network Flows for Vehicle Routing Problems

Invited abstract in session WA-58: MILPs for Vehicle Routing 2, stream VeRoLog - Vehicle Routing and Logistics.

Wednesday, 8:30-10:00
Room: S07 (building: 101)

Authors (first author is the speaker)

1. Konstantin Pavlikov
Department of Business and Management, University of Southern Denmark
2. Niels Christian Petersen
Department of Business and Economics, University of Southern Denmark

Abstract

This paper revises the two-commodity network flow modelling approach for the Capacitated Vehicle Routing Problem (CVRP) with identical vehicles. The flows of equally sized two commodities considered in this paper are organized in the opposite directions along the collection of routes assigned to vehicles. The resulting mathematical programming formulations allow to formulate a general, asymmetric CVRP (even with presence of Time Windows constraints) using n(n - 1)/2 binary variables, where n is the number of customers involved in the definition of CVRP, which is the number of binary variables typically required for the symmetric CVRP only. The commodity flow formulations of the problem is a very flexible tool for modeling the problem that allows for various enhancements. For example, the family of Generalized Large Multistar valid inequalities can be incorporated in a commodity flow-based formulation of the problem without
using a single extra constraint. In addition, the compact mathematical formulations of the problem are further improved using Rounded Capacity Inequalities at the root node. The computational study demonstrates that a wide range of problem instances from the literature can be solved to optimality (or suboptimality with relatively small optimality gaps) using a simple solution methodology that solely employs a standard mixed integer linear programming solver.

Keywords

Status: accepted

Back to the list of papers