$$
\newcommand{\B}{\mathbb{B}}
\newcommand{\R}{\mathbb{R}}
$$

Canberra was founded in 1913 by American architect Walter Burley Griffin, it is a vast, planned city built as a collection of towns separated by green belts.

**Canberra:**381,488 hab.

814.2 km² (428.6/km²)**Montréal (City):**1,649,519 hab.

431.50 km² (4,517.6/km²)**Montréal (Metro):**4,127,100 hab.

4,258.31 km² (898.1/km²)

- Demand is too spread out
- Most buses run almost empty
- Very high cost: almost 100 bus lines
- Service is not regular, esp. off-peak

- Booking system, trips start at a bus stop
- Low waiting time (15min preparation time)
- High frequency buses (aiming for every 15min)
- Shuttles for "first" and "last mile"

- One week of data (Monday to Saturday)
- 2,800 bus stops
- 21,000 trips for 60,000 passengers
- Two sets of hubs: $H_{10}$ and $H_{20}$

The Hub-Arc Location Problem [1] (HALP) is a variant of the well-known Hub Location Problem where hubs do not form a complete graph.

The Hub-Arc Location Problem [1] (HALP) is a variant of the well-known Hub Location Problem where hubs do not form a complete graph.

The HALP is used when designing networks where opening links between hubs has a cost but these links provide economies of scale (e.g., transhipping networks).

**Costs is a mix of expenses and time**, conversion factor $\alpha$- Taxis $x$ available everywhere to route trips, combination of time and cost: $$\tau = (1 - \alpha) d_{ij} \cdot T + \alpha \cdot t_{ij}$$
- Bus legs (hub arcs) $z$ with a fixed installation cost: $$\beta = (1 - \alpha) d_{hl} \cdot B$$
- Bus trips $y$ between hubs, only cost $$\gamma = \alpha (t_{ij} + S)$$

$$
\begin{align}
\min && \sum_{r \in T} \sum_{i,j \in N} \tau_{ij}^r x_{ij}^r + \sum_{r \in T}\sum_{h, l \in H} \gamma_{hl}^r y^r_{hl} & + \sum_{h,l \in H} \beta_{hl} z_{hl} \\
s.t. && \sum_{l \in H} z_{hl} & = \sum_{l\in H} z_{lh} & \forall h \in H \label{eq:hub} \\
& & y^r_{hl} & \leq z_{hl} & \forall r\in T, \forall h,l \in H \label{eq:hard} \\
& & \sum_{j \in N} \left( x^r_{ij} - x^r_{ji} \right) + \sum_{\substack{h \in H \\ \text{if } i \in H}} \left(y^r_{ih} - y^r_{hi} \right) & = 1, 0, -1 & \forall r \in T, \forall i \in N \\
& & x_{ij}^r, y_{hl}^r \geq 0; z_{hl} \in \B
\end{align}
$$

Some trips will never use the bus network, whatever the configuration!

About 30% of trips can just be omitted in the model when using 10 hubs; 20% with 20 hubs.

We have an upper bound on the cost $\tau_{od}$, let us remove any "best" scenario above that:

if $\tau_{oh} + \gamma_{hl} + \tau_{ld} > \tau_{od}$, then remove $x_{oh}$ and $x_{ld}$.

55% to 58% reduction in the number of $x$ variables.

**$H_{10}$ has 130,000 $x$ variables, $H_{20}$ has 300,000.**

- Take a MIP
- Project out continuous variables
- You obtain two problems: a master and a sub-problem

The HALP can actually be seen as a two-level decision process.

- 1. Which arcs to open
- 2. How to route the flow

- The master is a relaxed problem, it fixes the integer variables
- Solve the dual LP with the candidate solution to generate cuts
- Instead of having to explore all solutions, only add "relevant" constraints

$$
\begin{align}
\max && u_o - u_d - \sum_{h, l \in H} & \bar{z}_{hl} v_{hl} \\
s.t. && u_i - u_i & \leq \tau_{ij} & \forall i,j \in N \\
&& u_h - u_l - v_{hl} & \leq \gamma_{hl} & \forall h,l \in H \\
&& u, v \geq 0
\end{align}
$$

One issue with min-cost flow, as with many "network" problems, is its high degeneracy: multiple equivalent optimal solutions.

So we design a Pareto optimal sub-problem.

- Modify the objective function using a core point
- Add a constraint to restrict the solution space with the solution of the primal problem

$$
\begin{align}
\max && u_o - u_d - \sum_{h,l \in H} & z^0_{hl} v_{hl} \\
s.t. && u_i- u_j & \leq \tau_{ij} \quad \forall i,j \in D^r \\
&& u_h - u_l - v_{hl} & \leq \gamma_{hl} \quad \forall h, l \in H \\
&& u_o - u_d - \sum_{h,l \in H} \bar{z}_{hl} v_{hl} &= spp(o, d, \bar{Z}) \\%
&& u \geq 0, v \geq 0
\end{align}
$$

With fixed $z$, the sub-problem becomes a collection of independent min-cost flows.

We need to decide how we are going to "bundle" the cuts.

- All in one
- By origin
- By leg used
- By closest hub
- One per trip

Papadakos [3] showed that the choice of a core point can dramatically influence the performance of Pareto approach. Even better when updating it. $$ z^{0 (n + 1)}_{hl} = \frac{z^{0 (n)}_{hl} + \bar{z}^{(n)}_{hl}}{2} $$

Thank you for your attention.

Paper available
arXiv:1601.00367 [cs.AI]