# Capacitated Vehicle Routing Metaheuristics Or Column Generation using python to solve the math optimization problem CS 286P Final Project

Capacitated Vehi

Capacitated Vehicle Routing Metaheuristics Or Column Generation using python to solve the math optimization problem CS 286P Final Project

Capacitated Vehicle Routing

Metaheuristics or Column Generation

Amelia Regan, Julian Yarkony

December 2, 2021

1 The Problem

We now consider the Capacitated Vehicle Routing Problem (CVRP) which is defined as follows. We are

given a set of items, and a starting/ending depot embedded in a metric space. Each item is associated with

an integer demand and the vehicles have a common capacity. We seek to partition the items into ordered

lists of items called routes each serviced by a unique vehicle so as to minimize the total distance traveled

while ensuring that no vehicle services more demand than it has capacity. The number of vehicles used is

bounded.

We now consider the mathematical description of the CVRP. We use N to denote the set of items, which

we index by u. We define N+ to be N augmented with the starting depot, and ending depot which are

denoted −1,−2 respectively (and are typically the same place). Items and depots are embedded on a metric

space, and hence distances between them satisfy the triangle inequality. We use cuv to denote the distance

between any pair of u, v each of which lie in N+. Each item is associated with an integer demand du, which

1

lies in the set of unique demands D where D0 is the capacity of a vehicle. A route is feasible if it satisfies

the following.

• The route starts and ends at the starting/ending depot respectively.

• The route visits an item no more than once.

• The route services total demand that does not exceed D0.

We denote the set of routes with Ω, which we index by l. We describe the mapping of items to routes using

aul ∈ {0, 1} where aul = 1 if and only if route l contains item u for any u ∈ N. For short hand we use

Nl = {∀u ∈ N s.t. aul = 1} meaning that Nl is the set of items serviced by l. For any u, v pair where each

lie in N+ we set auvl = 1 IFF v follows u immediately in route l and otherwise set auvl = 0. The cost of a

route is denoted cl is defined as the total distance traveled, which we write formally as follows.

cl =

∑

u∈N+

v∈N+

cuvauvl ∀l ∈ Ω (1)

The constraint that a route services no more demand than D0 is written below using du to denote the demand

of item u.

∑

u∈N

duaul ≤ D0 ∀l ∈ Ω (2)

A set of routes provides a feasible solution to CVRP if it services every item at least once and uses no more

than K routes where K is the number of vehicles available. We describe a solution to CVRP using decision

variables θl ∈ {0, 1} where θl = 1 indicates that route l is selected and otherwise θl = 0. We write the

selection of the optimal solution below as follows with annotation describing the equations subsequently.

min

θ∈{0,1}

∑

l∈Ω

clθl (3a)

∑

l∈Ω

aulθl ≥ 1 ∀u ∈ N (3b)

∑

l∈Ω

θl ≤ K (3c)

In (3a) we seek to minimize the total cost of the routes selected. In (3b) we ensure that every item is covered

at least once. We should note that in any optimal solution that each item is covered exactly once since cl

increases as Nl grows. In (3c) we enforce that no more than K routes are used.

2

2 The Assignment

2.1 Option I.

• 1. Develop the metaheuristic of your choice to solve this problem.

• 2. Some suggestions:

– GRASP

– Genetic Algorithm

– Ant Colony Optimization

– Tabu Search

• 3. Whatever choice you make, you will need to examine some of your implementation choices.

– Parameters are choices but we are interested in

– Route construction choices

– Post processing route improvement choices

2.2 Option II.

Continue your exploration of Column Generation by implementing a simple version of that method.

Below we discuss how to go about that.

We solve (3) via solving the linear programming (LP) relaxation, which is referred to as the master

problem (MP). This LP relaxation is very tight in practice. We write the MP below with dual variables

written in brackets ([]) after the equations.

min

θ≥0

∑

l∈Ω

clθl (4a)

∑

l∈Ω

aulθl ≥ 1 ∀u ∈ N [πu] (4b)

∑

l∈Ω

θl ≤ K [−π0] (4c)

We write the dual form of (4) below.

max

π≥0

−Kπ0 +

∑

u∈N

πu (5a)

cl + π0 −

∑

u∈N

aulπu ≥ 0 ∀l ∈ Ω (5b)

3

Since the set of routes (Ω) grows exponentially in the number of items we cannot trivially solve (4).

Instead column generation (CG) is employed to solve (4). CG constructs a sufficient subset of Ω denoted

ΩR s.t. solving (4) over ΩR provides an optimal solution to (4) over Ω. To construct ΩR, we iterate

between (1) solving (4) over ΩR, which is referred to as the restricted master problem (RMP) and (2)

identifying variables with negative reduced cost, which are then added to ΩR. Typically the lowest

reduced cost column is generated. We write the selection of this column as optimization below using

c̄l to denote the reduced cost of column l.

min

l∈Ω

c̄l (6a)

c̄l = cl + π0 −

∑

u∈N

aulπu (6b)

The operation in (6) is referred to as pricing. One or more negative reduced cost columns are generated

during pricing. CG terminates when pricing finds no column with negative reduced cost. This certifies

that CG has produced the optimal solution to (4). We write pricing as an integer linear program

(ILP) in Appendix 2.2.1 though it is often solved with a resource constrained shortest path solver (?).

We terminate CG when no l in Ω has negative reduced cost. CG initializes ΩR with a heuristically

generated feasible integer solution or using artificial variables that have prohibitively high cost but

ensure a feasible solution. In Alg 1 we describe CG in pseudo-code.

4

Algorithm 1 Basic Column Generation

1: ΩR ← from user

2: repeat

3: Solve for θ, π using (4),(5) over ΩR

4: l∗ ← minl∈Ω c̄l

5: ΩR ← ΩR ∪ l∗

6: until c̄l∗ ≥ 0

7: Return last θ generated.

2.2.1 Pricing as an Integer Linear Program

We now consider the solution to pricing 6 as an integer linear program (ILP).

We use decision variable xuvd if the generated route services u then v and contains exactly d units of

demand after leaving u. The following combinations of u, v, d exist

– xuvd exists if dv ≤ d ≤ D0 −du where d−1 = d−2 = 0

The set of valid combinations of u, v, d is denoted P . We define c̄uv to be the cost of traveling from u

to v minus the additional cost corresponding to dual variables.

c̄uv = cuv −πv∀(u, v, d) ∈ P, v ̸= −2 (7a)

c̄uv = cuv + π0∀(u, v, d) ∈ P, v = −2 (recall v=-2 is the end depot) (7b)

We write the lowest reduced cost resource constrained shortest path as pricing below in the form of an

ILP which we annotate below.

min

x∈{0,1}

∑

u,v,d∈P

c̄uvxuvd (8a)

∑

u,v,d∈P

xuvd ≤ 1 ∀u ∈ N (8b)

∑

−1,v,d∈P

x−1vd ≤ 1 (8c)

∑

u∈N

xuvd =

∑

u∈N

xv,u,d−dv ∀v ∈ N, d ≥ dv (8d)

In (8a) we minimize the reduced cost of the route. In (8b) we ensure that an item is visited no more

than once. In (8c) we ensure that up to no more than one route is selected by ensuring that no more

than one unit of flow leaves the start depot. In (8d) we ensure that the solution describes a route by

enforcing the flow constraint.

5

We should note that for small problems, the solution of (8) can be solved using a commercial solver

such as Gurobi or C-Plex but for larger problems we would develop our own solutions.

6

3 Results

Present your results in the following way:

– Introduction – Discuss the heuristic you are using (or CG)

– Discuss Sources of Information – Papers, Codes

– Discuss any choices you made for the metaheuristics (parameters, route construction, route im-

provement, parallelization etc.)

– Present your results (see the table below)

– Summarize – Discuss any insights gained

– Discuss the role of each member of the group in the project

– Include Your codes

Problem Instance Objective Function Value Best known Solution Time to Solution

P1 OFV BKS time

P2 OFV BKS time

4 Example Problem Instance

Name : Y-n25-k5

Comment : From Graph Generation Paper 5 Vehicles

TYPE : CVRP

DIMENSION : 30

Capacity: 7

NodeCoordSection

1 23 33

2 29 7

3 1 10

4 31 19

5 31 42

6 31 5

7 48 42

8 35 5

9 18 49

10 22 24

11 35 49

12 4 31

13 34 37

7

14 34 2

15 11 15

16 7 7

17 16 15

18 19 6

19 29 16

20 22 21

21 50 4

22 6 35

23 11 29

24 9 14

25 33 27

26 13 5

27 24 29

28 13 47

29 8 16

30 6 34

DemandSection

1 1

2 1

3 1

4 1

5 1

6 1

7 1

8 1

9 1

10 1

11 1

12 1

13 1

14 1

15 1

16 1

17 1

18 1

19 1

20 1

8

21 1

22 1

23 1

24 1

25 1

26 1

27 1

28 1

29 1

30 1

DepotLocation: 28, 36

EOF

You will also test your codes on problems from http://vrp.galgos.inf.puc-rio.br/index.php/en/

A-n32-k5

A-n54-k7

A-n55-k9

A-n60-K9

B-n50-k7

B-n56-k7

B-n63-k10

B-n54-k9

Golden17

Golden18

Golden19

Golden20

9

The Problem

The Assignment

Option I.

Option II.

Pricing as an Integer Linear Program

Results

Example Problem Instance