Lecture VII - Library Routing Optimization
Applied Optimization with Julia
Introduction
Central Libraries
Question: Anybody an idea what a central library is?
Central Libraries
- Book Delivery to Libraries in Germany
- They supply all local libraries within the same state
- Complex, as the number of libraries per state can be large
- Books and media in the libraries change often
- Customers can request books from other libraries
Structure of the Deliveries
- For delivery, central has several employees and cars
- Local libraries differ in size, some receive more items
- Items are collected as well during the tours1
- They are transported back to the central library
Potential Decisions
Question: What decisions can the library make for tours?
- Subdivide their set of libraries into several ordered tours
- Decide in which order to visit the libraries
- Evaluate which car to use for each of the tours
- Decide which driver to assign to each of the tours
Impact of the Decisions
Question: What is the impact of the decisions?
- Longer driving routes increase the footprint of the deliveries
- Suboptimal tours can lead to unnecessary costs
- Fuel, personnel, and repairs are increased
- Unhappy customers due to waiting times on ordered books
Have you heard of
this problem before?
Problem Structure
Objective
Question: What could be the objective for central libraries?
- Lowering costs through improved tours
- Improvement of their footprint through shorter tours
- Faster fulfillment of the deliveries
Modelling
Question: What could we try to model?
Minimization of the travel time while supplying all libraries in the state and adhering to the vehicle capacities and driving time restrictions.
Capacitated
Vehicle Routing
(CVRP)
Vehicle Routing Problem
- CVRP is a subproblem
- Main problem is Vehicle Routing Problem (VRP)
- Problem class about designing routes for vehicle fleets
Note
There are many variants of the VRP! E.g., with time windows, periodic deliveries, allowing for pickups or deliveries, and much more!
Let’s visualize
the problem!
Problem Visualization
Basic Problem Setting
Basic Problem Setting with Arcs
Setting with Vehicles
Basic Problem Setting with Tours
Problem Structure
Available Sets
Question: What could be the sets here?
Available Parameters
Question: What are possible parameters?
Tip
Decision Variable(s)?
We have the following sets:
- All nodes, including the depot,
- All arcs between the nodes,
- The available vehicles,
Our objective is to:
Minimize the total travel time while supplying all customers and adhering to the vehicle capacities and duration restrictions.
Question: What could be our decision variable/s?
Decision Variables
Variable Domain
Question: Why this might make the problem difficult?
Decision Variable/s (again)?
We have the following sets:
- All nodes, including the depot,
- All arcs between the nodes,
- The available vehicles,
Our objective is to:
Minimization of the travel time (or driving distance), while supplying all customers and adhering to the vehicle capacities and duration restrictions. Hint: Even with many vehicles, each arc can maximally be passed once!
Decision Variables (again)
Question: What could be our decision variable/s?
Only possible under certain conditions!
Only possible, if time and capacity constraints are equal for all vehicles!
Model Formulation
Objective Function?
Our objective is to:
Minimization of the travel time (or driving distance), while supplying all customers and adhering to the vehicle capacities and duration restrictions.
Question: What could be our objective function?
We need the following variable:
Objective Function
We need the following parameters:
Question: What does
Problem Constraints
Constraints?
Question: What constraints do we need?
- Each customer has to be visited once
- The depot has to be entered and left
- We have to enforce the capacity of our vehicles
- We have to ensure the maximal duration of each tour
Subtours
In addition, we have to prevent subtours!
What is a
subtour?
Subtours
Constraints
Visit Each Customer Once?
The goal of these constraints is to:
Ensure that each customer is visited exactly once. Essentially, we could also say that each node has to be entered and left exactly once.
We need the following sets and variables:
Visit Each Customer Once
Question: What could the constraint look like?
Question: Why for all nodes except the depot?
The depot is the only node that is visited multiple times!
Depot Entry and Exit Constraints?
The goal of these constraints is to:
Ensure that each vehicle enters and leaves the depot exactly
We need the following sets and variables:
Question: What could the constraint look like?
Depot Entry and Exit Constraints
Are all constraints necessary?
No, theoretically we could also say that we only have to leave or enter the depot exactly
Capacity and Subtour Elimination
The next ones are
a little bit tricky.
MTZ Formulation
- Miller-Tucker-Zemlin (MTZ) Constraints
- Formulation by Kara, Laporte, and Bektas (2004)
- Prevent subtours and track routes and capacity utilization
- First, we need an additional variable!
Note
You don’t need to guess these constraints, as they are quite tricky!
MTZ Constraints
We need the following sets, parameters, and variables:
Too
complicated?
Don’t worry!
- Let’s break it down!
- Capacity
No connection between nodes
- In case
- Non-binding for relation between two nodes
- Following is perfectly fine:
Connection between two nodes
- In case
- Binding for relation between two nodes
- Can be summarized to:
Connection in more detail
Question: Why is it binding?
- Binding as
- Hence, fullfiled if the demand of
Question: Do you get the idea?
- If
- If
Tour from the Depot
- Tour of vehicle A ok
- Depot is the only node visited multiple times
- But the constraints are not applied here!
Tour on its Own
- Let’s start at node
- We drive to node
Tour on its Own II
- We continue to node
Tour on its Own III
- We continue to node
- Connection from
- Infeasible solution!
Subtour Elimination
- Connection in the other direction wouldn’t work as well
- Only depot as “reset” , as constraints are not applied here
Question: What about the capacity?
- Remember variable domain of
Last Constraint
Ensure time limit?
Question: Anybody an idea?
- Constraints basically follow the same idea!
- First, we again need an additional variable
Ensure time limit
We need the following sets and variables:
Any questions?
Asymmetric Vehicle Routing Problem
Objective
The goal of the objective function is to:
Minimize the total travel distance.
Each customer is visited once
Our constraints ensure:
Each customer is visited exactly once.
Depot entry and exit
Our constraints ensure:
The depot is visited by exactly
Capacity and subtour elimination
Our constraints ensure:
The capacity limit is respected and subtours are eliminated.
Time constraints
Our constraints ensure:
The time limit is respected (and subtours are eliminated).
Variables
The variable domains make sure that:
The binary setup variable is either 0 or 1 and the new variables are below the time and capacity limit.
Model Characteristics
Characteristics
Questions: On model characteristics
- Is the model formulation linear/ non-linear?
- What kind of variable domains do we have?
- What do you think, can the model be solved quickly?
Model Assumptions
Questions: On model assumptions
- What assumptions have we made?
- What are likely issues that can arise if the model is applied?
- Have we considered service times?
Extensions of the CVRP
Questions: What extensions do you know?
- time windows (TW)
- soft time windows (STW)
- multiple depots (MD)
- heterogeneous fleet (HF)
- backhauls (B)
- pickup and delivery (PD)
Implementation and Impact
Case Study in Schleswig-Holstein
- 165 libraries
- 119 visited biweekly
- Up to 9 different tours
- Time-Limit of 8 hours for each tour
Current Routing Plan
Can our formulation
solve the problem
on a real-world instance?
No, although we can find
solutions within one hour,
the gap is still very large
with 40%-45%.
Problem is NP-hard
- We have already seen that a problem can be NP-hard
- Likely, that there are no polynomial-time algorithms
- Doesn’t mean that it can’t be solved!
Note
We won’t go deeper into this, but feel free to ask me!
Can we do
anything to solve
the model?
Heuristics
- We can still solve the problem with a heuristic
- Likely not the optimal solution, but a lot of research goes into efficient algorithms to solve these problems
- In our case study we applied Hybrid Genetic Search for the CVRP (HGS-CVRP) by Vidal (2022)
Tip
For problems with 100+ locations, heuristics are often the only practical choice.
Applications Beyond Libraries
Logistics & Delivery
- Package delivery
- Food delivery services
- Grocery delivery
- Mail distribution
Service Industries
- Maintenance crews
- Home healthcare visits
- Waste collection
- School bus routing
Question: Can you think of other applications?
Conclusion
- Standard problem that occurs in many different places
- Solving the problem with a mathematical model is difficult
- Nowadays, there are many good heuristics
- Many companies are working on the problem
And that’s it for todays lecture!
We now have covered the Capacitated Vehicle Routing Problem and are ready to start solving some tasks in the upcoming tutorial.
Questions?
Literature
Literature I
For more interesting literature to learn more about Julia, take a look at the literature list of this course.
Literature II
Lecture VII - Library Routing Optimization | Dr. Tobias Vlćek | Home