An Improvement MIP model for Routing Problems
Simen T. Vadsetha,∗ , Henrik Anderssona and Magnus Stålhaneaa Norwegian University of Science and Technology, Trondheim, Norway

simen.t.vadseth@ntnu.no∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 12, 2022
Keywords: (Vehicle Routing, Matheuristic, Inventory Routing Problem, Production Routing
Problem, Capacitated Vehicle Routing Problem)

1Introduction

Vehicle routing problems are well-studied within the field of transportation science, and theyexist in a variety of versions with numerous solution methods. Three relevant versions are
the capacitated vehicle routing problem (CVRP), the inventory routing problem (IRP) and theproduction routing problem (PRP). In the CVRP, a set of customers with a known demand fora product needs to be served by a fleet of vehicles with inventory capacities. The vehicles startat a depot which they return to at the end of the day. All customers must be visited and all
demands must be fulfilled. In the IRP, there is a time horizon consisting of several days. Eachcustomer has a storage of the product which they consume over time. The customers’ storage isrefilled by the producer and transported by a set of vehicles and customers are not allowed toexperience stock-outs. The aim is to minimize both inventory costs and routing costs. The PRP
is similar to the IRP, but here we control the production at the depot where the vehicles pickup the product as well. We refer to the surveys of Laporte (2009) and Adulyasak et al. (2015)
for more details on the CVRP, IRP and PRP.
Most vehicle routing problems have in common that they are very hard to solve. One way tomodel vehicle routing problems is to introduce a route set R consisting of every possible route.
Here, a route is just a string of customer nodes. We then choose which routes in R we should
use in order to solve the problem. We call this a path-flow formulation. However, we can replace
R with a much smaller route set R′ and still obtain the optimal solution as long as R′ includes
the optimal routes. Vadseth et al. (2021) and others have used this successfully in matheuristics.
However, finding the correct routes is not trivial and small alterations from the optimal routes
can lead to low-quality solutions.
Hence, to overcome the aforementioned challenges we introduce a mixed integer programming(MIP) model to help us solve routing problems with a route set R′ , but where we can make smallerchanges to the routes in addition. We call this an improvement MIP model. The route set R′ caneither consist of the routes from a previously found solution or multiple solutions. We have used
this improvement MIP model as part of a matheuristic for both the IRP and the PRP (Vadsethet al., 2022) and to improve the best-known solution for several known benchmark instances for
the CVRP. The improvement MIP model can also easily be adapted to other vehicle routing
problems.
TRISTAN XI Symposium

Original abstract submittal

S.T. Vadseth, H. Andersson and M. Stålhane22An Improvement MIP Model

The improvement MIP model presented here is a modified version of a path-flow model for theCVRP with a set of routes R̂. Here, the model has the possibility of modifying the chosenroutes by inserting or removing customers. The improvement MIP model calculates the exact
costs of altering the original routes and does so even in cases where multiple changes are madesimultaneously. The presented improvement MIP model for the CVRP is similar to the modelfor the PRP presented in Vadseth et al. (2022). Please note that Improvement MIP is reduced
to an IP for the CVRP.
We start by assuming that no customers are visited by a route and then insert the customerthat should be visited. The variable yr is 1 if route r is used, and 0 otherwise. In addition, thevariable xir is 1 if node i is inserted into route r, and 0 otherwise. The cost of using route r isN . The parameter Q is
denoted CrR , and the cost of inserting node i into route r is denoted Cir
the vehicle capacity and Di is customer i’s demand. In addition, N ′ is the set of all customer
nodes.

minXr∈R̂

X

CrR yr +XX

N
Cir
xir ,

(1)

i∈N ′ r∈R̂Di xir ≤ Qyr ,r ∈ R̂,(2)X

xir = 1,i ∈ N ′,(3)

xir ≤ yr ,i ∈ N ′ , r ∈ R̂,(4)yr ∈ {0, 1},r ∈ R̂,(5)

xir ∈ {0, 1},i ∈ N ′ , r ∈ R̂.

(6)i∈N ′r∈R̂

The objective function (1) minimizes the transportation costs, while constraints (2) ensurethat a vehicle cannot deliver more than its maximum capacity. In addition, constraints (3) makesure that a customer can only be visited by at most one vehicle. The fact that a customer cannot
be added to an unused route is taken care of by constraints (4). Constraints (5)-(6) define thevariable domains. In addition, several instances have requirements regarding the minimum ormaximum number of vehicles used.
To keep the transportation cost in the improvement MIP model correct with respect to thecost in the original problem, we introduce additional constraints to limit the number of changes
that can be made to a route, and also on the type of changes. Without these limitations, somechanges might look beneficial in the improvement MIP model but are actually disadvantageous
to the solution of the original CVRP. To present these constraints some additional notation isintroduced. The cost of traveling between nodes i and j is denoted Cij .The original route r
includes P r customer visits, and we use p = 0 and p = P r + 1 to denote the depot at the startand end of r. The set of customers visited by the original route r is denoted N r . The functionir (p) returns the node placed in position p in route r. Moreover, the function pr (i) returns
the position of node i in route r if i was originally in r. If i was not originally in r however,pr (i) = argmin(Cir (p−1),i + Ci,ir (p) − Cir (p−1),ir (p) |p = 1, . . . , P r + 1) returns the position of agreedy insertion of i into r. Lastly, we introduce the parameter Aipr which is 1 if node i is placedor would be greedily placed in position p in r, and 0 otherwise. Figure 1 illustrates the notation.
The variable x0r is defined to be equal to 1.
TRISTAN XI Symposium

Original abstract submittal

S.T. Vadseth, H. Andersson and M. Stålhane30eair (2) = bpr (b) = 2 bRoute rPr = 4d Apr (e) = 5d4r = 1

cFigure 1 – Illustration of a route r, the functions ir (p) and pr (i) and the parameter Aipr .

The following constraints are added to the formulation to ensure that the transportation cost
is correctly calculated.
xir (pr (i)−1),r + xir (pr (i)),r ≥ 2xir
XAipr xir ≤ 1r ∈ R̂, i ∈ N ′ \ N r(7)r ∈ R̂, p ∈ 1, . . . , P r + 1(8)r ∈ R̂, i ∈ N r(9)i∈N ′ \N r

xir + xir (pr (i)+1),r ≥ yrConstraints (7) state that if a node i that was originally not in route r is inserted, then wemust include the nodes that are located before and after the position where node i is inserted
into r. Constraints (8) ensure that at most one node, not originally in route r, can be inserted
into the same position in r. Constraints (9) make sure that if route r is used, then either node ior its successor, which are both in N r , must be included in the route.
N for node i in route r the following formulas are used:
To calculate the insertion cost CirNCir= Cir (pr (i)−1),i + Ci,ir (pr (i)) − Cir (pr (i)−1),ir (pr (i))
N
Cir
= Cir (pr (i)−1),i + Ci,ir (pr (i)+1) − Cir (pr (i)−1),ir (pr (i)+1)

The route cost, CrR , for route r is given by the formula:
XN
CrR = CrT −Cirr ∈ R̂, i ∈ N ′ \N r

(10)

r(11)

r ∈ R̂, i ∈ N(12)i∈N rHere, CrT is defined as the cost of the original route without any changes. Hence, both theinsertion cost and the route cost depends on the nodes included in the original route. Figure 2
shows the cost calculations of a route in the improvement model. The original route is marked
with dotted arrows. After solving the improvement model, route r is included in the solution,
but changes have been made to it. The new route is marked with solid arrows.

3

Results

The improvement MIP model has been tested as an essential part of a matheuristic for thePRP and IRP. The matheuristic was tested on two sets of benchmark instances for the PRP
from the literature. The first set was introduced by Archetti et al. (2011) and consists of smaller
instances, while the larger set was introduced by Boudia et al. (2007). For the Archetti instances,the matheuristic found the best-known solution for 516 out of 960 instances. Further, for theBoudia instances, the matheuristic found the best-known solution for 75 out of 90 instances. On
the large multi-vehicle benchmark instances for the IRP released by Archetti et al. (2012) themethod found the best-known solution for 93 out of 240 instances. See Vadseth et al. (2022) for
more details.
TRISTAN XI Symposium

Original abstract submittal

S.T. Vadseth, H. Andersson and M. Stålhane0ea

Route rdbc4

CrT = C0a + Cab + Cbc + Ccd + Cd0
N =C +C −C
N =C +C −CCarCbr0aacab0babbc
NNCcr = Cbc + Ccd − Cbd
Cdr = Ccd + Cd0 − Cc0
N =C +C −CCere0
ded0
N − CN − CN − CN
CrR = CrT − Carcr
brdr= C0b + Cac + Cbd + Cc0 − Cab − Cbc − Ccd
N + CN + CN0 → b → d → e → 0 : CrR + Cbrerdr= C0b + Cbd + Cde + Ce0

Figure 2 – Example showing the cost calculations when b, d and e are included in route r anda and c are excluded. The route cost CrR is calculated based on the original route, the cost ofchoosing route r and include b, d and e is shown to be correct.

For the CVRP, the improvement MIP model was tested on the large benchmark instances
released by Arnold et al. (2019) and where the route set R̂ was made up by the routes from thebest-known solution. The improvement MIP model improved the best-known solution of five outof ten instances, and at a later stage six out of ten instances. See http://vrp.atd-lab.inf.
puc-rio.br/index.php/en/ for more details.

References
Adulyasak, Yossiri, Cordeau, Jean-François, & Jans, Raf. 2015. The production routing problem: A
review of formulations and solution algorithms. Computers & Operations Research, 55, 141–152.
Archetti, Claudia, Bertazzi, Luca, Paletta, Giuseppe, & Speranza, M Grazia. 2011. Analysis of themaximum level policy in a production-distribution system. Computers & Operations Research, 38(12),1731–1746.
Archetti, Claudia, Bertazzi, Luca, Hertz, Alain, & Speranza, M Grazia. 2012. A hybrid heuristic for an
inventory routing problem. INFORMS Journal on Computing, 24(1), 101–116.
Arnold, Florian, Gendreau, Michel, & Sörensen, Kenneth. 2019. Efficiently solving very large-scale routing
problems. Computers & operations research, 107, 32–42.
Boudia, Mourad, Louly, Mohamed Aly Ould, & Prins, Christian. 2007. A reactive GRASP and pathrelinking for a combined production–distribution problem. Computers & Operations Research, 34(11),3402–3419.
Laporte, Gilbert. 2009. Fifty Years of Vehicle Routing. Transportation Science, 43(4), 408–416.
Vadseth, Simen T, Andersson, Henrik, & Stålhane, Magnus. 2021. An iterative matheuristic for theinventory routing problem. Computers & Operations Research, 131.
Vadseth, Simen T, Andersson, Henrik, Chitsaz, Masoud, & Stålhane, Magnus. 2022. A multi-start route
improving matheuristic for the production routing problem. Working paper.

TRISTAN XI Symposium

Original abstract submittal