Calculating Economical
Visually Attractive Routes

C. Gretton & P. Kilby

Capacitated VRP
with Time Windows

• Service a number of customers with a fleet of vehicles
• Minimise: (1) fleet size, and (2) total distance travelled
• Capacity constraints
• Time windows

Capacitated VRP
with Time Windows

• Service a number of customers with a fleet of vehicles
• Minimise: (1) fleet size, and (2) total distance travelled
• Capacity constraints
• Vehicles have bounded capacity
• Customers each have a demand
• Time windows

Capacitated VRP
with Time Windows

• Service a number of customers with a fleet of vehicles
• Minimise: (1) fleet size, and (2) total distance travelled
• Capacity constraints
• Time windows
• Customers must be serviced during specified intervals

Capacitated VRP
with Time Windows

• Service a number of customers with a fleet of vehicles
• Minimise: (1) fleet size, and (2) total distance travelled
• Capacity constraints
• Time windows
• NP-Complete -- e.g., TSP is a subproblem

Capacitated VRP
with Time Windows

• Service a number of customers with a fleet of vehicles
• Minimise: (1) fleet size, and (2) total distance travelled
• Industrial instances can only be solved approximately using metaheuristics: e.g. savings and insertion based
• We use a large-neighbourhood search (LNS)
• LNS naturally couples with other general constraints processing procedures

LNS -- Incumbent Solution

LNS -- Next, Visits are Removed

LNS -- Visits Inserted

LNS -- Background

• Objective is to minimise a weighted sum of quantities:
• Classical: Distance, Time, Overtime, etc.
• Non-Classical: Dispatch-Time Penalty, Slack Penalties, Surplus Penalties, Visual Unattractiveness, etc.
• While satisfying all "hard" constraints:
• Vehicle cannot be overloaded
• Customer must be serviced according to time windows
• LNS: Customers are removed according to a removal rule
• LNS:Customers assigned according to an insertion rule

LNS -- Background

• Objective is to minimise a weighted sum of quantities
• While satisfying all "hard" constraints...
• LNS: Customers are removed according to a removal rule
• More-or-less greedy wrt customer contribution to a weighted fragment of the objective value of the incumbent (and ease of exchange)
• LNS: Customers assigned according to an insertion rule
  • More-or-less greedy wrt regret scores -- Sum \(k=2..N\) of differences between objective values of best and \(k^{th}\) most promising insertion

Visually Attractive Routes

• LNS quickly produces short solutions
• Solutions are not robust
• And they are not visually attractive
• Long narrow tours are bad (cannot easily reschedule)
• Driver familiarity with all customers in their vicinity
• Difficult for human planners to reason about on-the-fly modifications to overlapping routes (e.g. callbacks)

Visually Attractive Routes

• Our clients cannot implement optimised routes
• They demand visually attractive routes

Example of Visual Attractiveness

	Routes	Route Hulls
Not Robust
Robust

Penalty for Lacking Visual Appeal

• Route Median Penalty
• \(d(i,j)\) is the symmetric distance between \(i\) and \(j\)
• Given a route \(R\), a visit \(i\) is a good candidate for the geographical centre of \(R\) if it has a relatively low score:
\[V(i,R) = \sum_{j \in R} d(i, j)\]
• The median of route \(R\) is a visit \(C_R \in R\) with the lowest \(V\) score, in other words:
\[C_R=\mathop{\arg\,\min}\limits_{i \in R} V(i, R)\]
• Route Median solution penalty is equal to the sum of distances of assigned visits to their route medians

Characterising Shape via Bending Energy

• Assume a route is a contour formed using a linear thin shelled medium
• Where \(K(p)\) is the curvature at point \(p\), the stored energy of a shape is therefore:
\[\int |K(p)|^2 \mathrm{d}p\]
• Nontrivial contours with minimum energy are circles
i.e. are very visually attractive...

Curvature and Polygonal Curves

• One defines the visual curvature at a point as follows:
\[K_{N, \Delta S}(p) = \pi \frac{\sum_{i=0}^{N-1} \#[H_{\alpha_i}(S(p))]}{N\Delta S}\]
• \(H_{\alpha_i}\) is a height function rotated by angle \(\alpha_i=\pi\frac{i}{N}\)
• \(\#[.]\) counts extreme points in the neighbourhood \(S(p)\) of size \(\Delta S\).
• In the limiting case this gives us a curvature familiar to differential geometry (Liu etal., IJCV 2008):
\[K(p) = \lim_{\Delta S \to 0} |\frac{\Delta\theta(p)}{\Delta S}|\]

Height Functions

• \(H_{\alpha_i}\) is a height function rotated by angle \(\alpha_i=\pi\frac{i}{N}\)

Polygonal Curves

• One defines the visual curvature at a point as follows:
\[K_{N, \Delta S}(p) = \pi \frac{\sum_{i=0}^{N-1} \#[H_{\alpha_i}(S(p))]}{N\Delta S}\]
• \(H_{\alpha_i}\) is a height function rotated by angle \(\alpha_i=\pi\frac{i}{N}\)
• \(\#[.]\) counts extreme points in the neighbourhood \(S(p)\) of size \(\Delta S\).
• Relating to differential geometry (Liu etal., IJCV 2008):
\[ \begin{array}{lcl} K(p) & = & \lim_{\Delta S \to 0} |\frac{\Delta\theta(p)}{\Delta S}| \\ & = & \lim_{\Delta S \to 0} \lim_{N \to \infty} K_{N, \Delta S}(p) \\ \end{array} \]

Polygonal Curves

• One defines the visual curvature at a point as follows:
\[K_{N, \Delta S}(p) = \pi \frac{\sum_{i=0}^{N-1} \#[H_{\alpha_i}(S(p))]}{N\Delta S}\]
• \(H_{\alpha_i}\) is a height function rotated by angle \(\alpha_i=\pi\frac{i}{N}\)
• \(\#[.]\) counts extreme points in the neighbourhood \(S(p)\) of size \(\Delta S\).
• In the polygonal case, for small enough \(\Delta S\) visual curvature gives us turn angles -- i.e., where \(\eta(p)\) is the turn angle at vertex \(p\):
\[\eta(p) = \Delta S \lim_{N \to \infty} K_{N, \Delta S}(p)\]
• After scaling so that \(\Delta S=1\)

Bending Energy as a Penalty

• Minimise the sum of turn angles.
• Both bending and median penalties can be added to the objective.
• The median penalty guides LNS to produce non-overlapping routes.
• The bending penalty mitigates the tendency of LNS to select for long and messy routes given the median penalty.

No Shape Penalties

LNS traces a short contour

Minimising Bending Energy

LNS traces concentric contours

Minimising Bending Energy

Scale Invariant and Invariant to Visit Count

Visual Comparison

	Median	No Median
Bending
No Bending

Experimental Evaluation

• Benchmarks: Solomon and Extended Solomon instances
• \(10^2\) to \(10^3\) customers
• Solomon and Desrosiers, 1988
• Gehring and Homberger, 1999
• \(10^4\) iterations of LNS on each instance
• Forbid dropping of any customers (via very large penalty)
• Relax time windows, by introducing late penalty proportional to earliness/lateness

Overview

• Benchmarks: Solomon and Extended Solomon instances
• \(10^2\) to \(10^3\) customers
• Optimising for the median penalty, baseline comparison:
• Area of intersecting hulls reduced by $43\%$ on average
• Average distance is \(13\%\) greater
• Average distance is on \(9\%\) up using bending energy \(^1\)
• Area of intersecting hulls is marginally greater
• Positive synergies in LNS with both bending energy and median penalties

---

• \(^1\) Tang and Miller-Hooks, 2006, observe $7.2\%$ longer routes in practice optimising a median penalty term

Computational Considerations
Median

• Computing a route median for each route encountered
• Median is invariant to route permutations
• For each partial route encountered during an insertion:
• Suppose customers are sorted lexicographically
• Index to cached median calculations of partial route
• Use cache to avoid repeating calculations
• In practice we maintain a route hash
• Maintenance is constant time per insertion/removal

Graphical Conclusions

	Routes	Route Hulls
Bending and Median
Median

Large Neighbourhood Search for Attractive Routes

• Empirically we find:
• Median: provides attractive routes, and combined with
• Bending energy: attractive and short routes
• Direction application of Bending energy for aerial visual search
• Our customers like our visually attractive routes!

Credits