Long-haul Transportation Network Design

TSP (Traveling Salesman Problem, 旅行商问题) is a special case of VRP (Vehicle Routing Problem) where we have only one vehicle. 其特点在于从一个点出发，经过所有点，最后回到出发点。目的是找到最短路径

Travel cost matrix ${c_{ij}}$, $i\in{1,2,…,n}$, $j\in{1,2,…,n}$

• Symmetry: $c_{ij} = c_{ji}$
• Triangle inequality: $c_{ij}\leq c_{ik}+c_{kj}$

• $\sum_{j\in N}y_{ij}=1, \forall i\in N$
• $\sum_{i\in N}y_{ij}=1, \forall j\in N$

• $\sum_{i\in S, j\in S}y_{ij}\leq

  S

  -1, \forall S\subset N,

  S

  \geq 2$

Last-Mile Delivery

Delivery route optimization

1. Strategic route planning
   • Service pattern, delivery day determination
   • Sales territories, routes
   • Master/fixed delivery routes
2. Tactical daily dispatching
   • Daily delivery route determination to deliver pre-sell orders

Heuristic Solution Methods

• Alternatives to exact optimization by MIP
• a heuristic solution may not minimize cost

where $c(T*)$ is the optimal cost, $c(T^H)$ is the cost of the heuristic solution. Define the Solution Optimiality Gap as: \(\frac{c(T^*)-c(T^H)}{c(T^*)}\)

Heuristic for TSP

• Greedy: make a “best choice” each iteration based on “current conditions”. Finalize that choice, and move on!

• Construction: start with no solution, and construct a feasible route $T^H$. For example

  • $T^{NN}$: Nearest Neighbor Solution
  • $T^{IH}$: Insertion Heuristic
    • Nearest Insertion
    • Farthest Insertion
    • Cheapest Insertion

Nearest Neighbor Heuristic

1. Start at a node (e.g. random) $P={s}$ (path)
2. Find the nearest node $j$ to $i$ (minimize $c_{ij}$), where $i=P[-1]$
3. Add $j$ to the end of $P$
4. Repeat 2-3 until all nodes are in $P$
5. Connect final

Nearest Insertion Heuristic

1. Start at an initial subtour $T={i_0,i_1,i_0}$, where $c_{i_0i_1}$ is the cheapest arc
2. Find the nearest node $j$ to $i$
   • For each $j$ not in $T$, compute $C(j)=\min_{i\in T}c_{ij}$
   • Insert $j$ with smallest $C(j)$
3. Insert $j$ with min insertion cost, that is, find $(i,k)\in T$ that minimize \(IC(i,j,k)=c_{ij}+c_{jk}-c_{ik}\)
4. Repeat 2-3 until all nodes inserted

Farthest Insertion Heuristic

1. Start at an initial subtour $T={i_0,i_1,i_0}$, where $c_{i_0i_1}$ is the largest arc
2. Find the "farthest" node $j$ to $i$
   • For each $j$ not in $T$, compute $C(j)=\min_{i\in T}c_{ij}$ (这里还是 min)
   • Insert $j$ with largest $C(j)$
3. and 4. same as Nearest Insertion Heuristic

可以看到, NI 与 FI 唯二的区别在于

1. 选择的起始 subtour 一个最近一个最远
2. 插入点的时候, 一个是离最近点的距离最近, 另一个是离最近点的距离最远

Cheapest Insertion Heuristic

1. Start at an initial subtour $T={i_0,i_1,i_0}$, where $c_{i_0i_1}$ is the largest arc
2. Find the cheapest node $j$ to $i$
   • For each $j$ not in $T$, compute $IC(j)=\min_{(i,k)\in T}IC(i,j,k)$
   • Insert $j$ with smallest $IC(j)$
3. Repeat 2 until all nodes inserted

Construction Heuristics for CVRP

1. Let initial solution consist of a single route for each customer $i: R_i={0,i,0}$
2. Calculate savings matrix: ${S_{ij}}$ where $S_{ij}=c_{i0}+c_{0j}-c_{ij}$
3. Process entries in savings matrix from largest savings value to smallest:
   • Let $(i,j)$ be largest unprocessed savings pair
   • Merge route ending at node $i$ with route beginning at node $j$ if:
     • Nodes $i$ and $j$ are on different routes
     • Node $i$ is last on its route, and $j$ is first on its route
     • Positive savings created: $S_{ij}>0$
   • Else:
     • Mark $(i,j)$ as processed

Define possible mergers using a pair of nodes $(i,j)$

• $i$ and $j$ are on two different route
• $i$ is the last node on its route, and $j$ is the first node on its route
• Combined demand of two routes less than vehicle capacity (or time)

CVRP Capacity Vehicle Routing Problem (CVRM … Model): more than one vehicle cuz \(Q < \sum q_i\)

DVRP Distance/Duration Vehicle Routing Problem: