Formulate Vehicle Routing Problem— Using GAMS
Solve Small-Scale Vehicle Routing Problem
Vehicle Routing Problem (VRP) is a combinatorial problem that determines the optimal path for vehicles to deliver goods from source to destination minimizing cost. Thus, it is formulated as a Mixed Integer Non-Linear Programming (MINLP) problem with a minimizing Objective function.
VRP generalizes the Travelling Salesman Problem (TSP).
Problem Description: Consider a network with N=6 nodes with E=10 edges connection these nodes as shown below. The goal is to find the path with the lowest cost connecting nodes A and F without making any sub-tours.
Solution: There are 16 possible paths that connect node A and F in the above diagram, which are A-B-C-F, A-B-C-E-F, A-B-C-D-E-F, A-B-D-C-F, A-B-D-C-E-F
A-B-D-E-F, A-C-F, A-C-E-F, A-C-D-E-F, A-C-B-D-E-F, A-D-B-C-F, A-D-B-C-E-F, A-D-C-F, A-D-C-E-F, A-D-E-C-F, and A-D-E-F. The optimal path is A-D-E-F with total cost = 4.
Mathematical Formulation:
The VRP formulation is provided into 2 segments:
- Single Source — Single Destination Problem
- Multiple Source — Multiple Destination Problem
Single Source — Single Destination Problem
A Vehicle Routing Problem where goods are delivered from a single destination to a single destination is termed as a single source-single destination problem. The mathematical formulation to the MINLP Problem is given below,
Equation 1 represents the objective function that computes the total cost to deliver goods from source to destination via an optimal path. Equation 2 ensures that the incoming and outgoing edges are different for each node. Equation 3 and 4 initiates and concludes the optimal path at source (S) and destination (N) nodes respectively. Equation 5 ensures that the number of incoming and outgoing edges from a node are equal, which in this case is equal to 1. Equation 6 and 7 eliminate any sub-tours using variable T which computes the delivery cost and binary variable X which is equal to 1 if goods are delivered from node i to node j, or 0 otherwise. Finally, equation 8 ensures that the variable X is binary.
Note: Equation 7 is non-linear, but can be linearized using Big-M constraints as follows,
Multiple Source — Multiple Destination Problem
A Vehicle Routing Problem where goods are delivered from multiple sources to multiple destinations is termed as a multiple source-multiple-destination problem. It can be considered as an extension to the single source single destination problem, where each source-destination combination is considered as a new route (r).
The mathematical formulation to the MINLP Problem is given below,
Equation 1 represents the objective function that computes the total cost to deliver goods from multiple sources to multiple destinations via optimal paths. Equation 2 ensures that the incoming and outgoing edges are different for each node and route. Equation 3 and 4 initiates and concludes the optimal path at multiple sources (Sr) and multiple destinations (Nr) nodes for all routes respectively. Equation 5 ensures that the number of incoming and outgoing edges from a node are equal, which in this case is equal to 1 for all routes. Equation 6 and 7 eliminate any sub-tours for routes r using variable T which computes the delivery cost and binary variable X which is equal to 1 if goods are delivered from node i to node j, or 0 otherwise. Finally, equation 8 ensures that the variable X is binary.
Note: Equation 7 is non-linear, but can be linearized using Big-M constraints as explained above.
It can be seen that each source-destination combination has a separate route. However, in reality, more than one destination can be served on a single route. It implies that one or more than one destination can be an intermediate node. This characteristic is not captured in the above problem for the sake of simplicity.
Let's run on GAMS
GAMS or General Algebraic Modeling System is a software to model and solve optimization problems. To obtain GAMS, visit here. Follow chapter 2 from the GAMS user manual to start modeling in GAMS.
The mathematical model in the GAMS environment for a single-source single destination and multiple-source multiple destinations is provided here and here respectively. Execute the models in the GAMS environment to see results provided next.
GAMS code for Single source — Single destination Vehicle Routing Problem:
GAMS code for Multiple sources — Multiple destination Vehicle Routing Problem:
Numerical Example: Generate the small size transportation cost matrix for N=5 nodes with E=20 edges.
- By solving the single source — single destination problem, the optimal path obtained is 1–2–3–5 having total cost = 13.
- By saving the multiple source — multiple destination problem, the optimal paths obtained are Route 1: 1–2–3–5 and Route 2: 3–1–2 having total cost=22.
The Concluding Note
Routing problems are very popular among academic and research communities. And searching Google Scholar, it can be found that a vast pool of variants and solution techniques has been developed over the decades. Thus, routing problems are rising a cliff very steep.
In this article, a small problem is taken into account to explain the mathematical model of a routing problem. To execute a large size problem, commercial solvers cannot be used due to resource constraints. To this end, switching up to heuristics/meta-heuristic such as the Genetic Algorithm, Particle Swarm Intelligence, Grey Wolf Optimizer, and many others can prove to be useful.
