MDVRP

An Efficient Variable Neighborhood Search with Tabu Shaking for a Class of Multi-Depot Vehicle Routing Problems

(Published in Computers & Operations)

We present a Variable Tabu Neighborhood Search (VTNS) algorithm for solving a class of Multi-Depot Vehicle Routing Problems including MDVRP, MDVRP with Time Windows (MDVRPTW), and Multi-Depot Open Vehicle Routing Problem (MDOVRP). Our computational tests on these three problems show that VTNS provides promising results competitive with state-of-the-art algorithms from the literature in terms of both solution quality and run time. Overall, we achieve six new best-known solutions in the MDVRP, one in the MDVRPTW, and four in the MDOVRP benchmark data sets.

The following Tables present the new best solution found by VTNS for six instances of MDVRP. one instance of MDVRPTW, and four instances of MDOVRP.

MDVRP:

Problem n m v OFV Input Solution Visualization
p08

p08*

 249

249

 2

2

 14

14

 4388.23

4369.95

pr02 96 4 4 1296.25
pr06 288 4 12 2674.07
pr07 72 6 3 1082.93
pr08 144 6 6 1664.6
pr10 288 6 12 2820.88

MDVRPTW:

Problem n m v OFV Input Solution Visualization
pr04 192 4 5 2814.34

MDOVRP:

Problem n m v_Total OFV Input Solution Visualization

p08

p08*

 249

249

 2

2

 26

27

2787.16

2776.12

p10 249 4 28 2482.32
pr05 240 4 24 1699.40
pr10 288 6 29 1969.35

 

* The solution reported for p08 when the demand of customers 58 and 143 is considered to be zero.

➤