p16 | Park and Bike Hub Location (Mobian)¶
See also
This problem is sourced from Ferchtandiker2025.
Note
We add implicit assumptions that all sets are non-empty, \(U, v_{sp} \geq 0\) and \(N \leq M\).
Description¶
Optimizing Park and Bike hub locations for sustainable urban mobility
Terminology A Park & Bike (P&B) hub (or hub) is a facility combining car parking and bike parking. However, not all parking facilities can be transformed into hubs. The suitability of a parking facility for conversion into a hub depends on several elements. These include the size, the location, the accessibility and the potential demand for bike parking in the surrounding area.
A Point of Interest (POI) is defined as a working location node or a place where people gather.
The highways around the cities have junctions from which cars can enter the city.
Data
The set of potential locations for the hubs is given. Moreover, the number of people on an average day that enter the city at a certain junction and must go to a certain POI is given. Also (car, bike) distances and times from one certain location to another location are given.
When do people not use a hub? There are several reasons why people will not use a hub:
Commuters do not use a hub when the extra time needed is too much. More precisely, people will not use a hub if the travel time from the junction to the hub plus the biking time from the hub to the POI minus the driving time from the junction to the POI is more than an acceptable extra time Δ.
Commuters do not want to bike too long. More precisely, people will not use a hub if the biking time from the hub to the POI exceeds a certain threshold (T).
Commuters will not use the bike (and therefore will not use the hub) if the distance from the hub to the POI is less than a minimum distance (D).
Commuters will not use a hub if the number of car kilometers saved is too small. More precisely, people will not use a hub if the distance from a junction to the POI minus the distance from that junction to the hub h is less than τ.
All these conditions make no value for commuters to use a P&B. It is estimated that r% of the commuters for which at least one hub exists for which the above 4 reasons do not hold, will use a hub.
Goal The goal is as follows: Develop a model that determines, given that in total N hubs may be opened, at which locations we should open a hub, such that the total number of commuters that will make use of a hub is maximized.
Formulations¶
Formulation a (valid)¶
See also
This formulation is sourced from Ferchtandiker2025 (formulation id: efficient).
Note
This is the aggregate (efficient) formulation.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
Number of existing hubs that must remain open (hubs 0..N-1) |
integer |
scalar |
|
Total number of hub locations (existing and potential new) |
integer |
scalar |
|
Number of Points of Interest (destinations) |
integer |
scalar |
|
Number of junction roads (commuter origins) |
integer |
scalar |
|
Commuter demand from junction s to POI p |
continuous |
|
|
Feasibility indicator: 1 iff junction-hub-POI triple is viable for Park and Bike use |
binary |
|
|
Maximum number of new hubs that can be opened |
integer |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
1 if hub h is opened, 0 otherwise |
binary |
|
|
1 if demand from junction s to POI p is covered by at least one open feasible hub, 0 otherwise |
binary |
|
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
Commuter demand is non-negative. |
\(v_{sp} \geq 0 \quad \forall s \in S, p \in P\) |
yes |
The number of existing hubs does not exceed total hubs. |
\(N \leq M\) |
yes |
The maximum number of new hubs is non-negative. |
\(U \geq 0\) |
yes |
Number of Points of Interest is positive. |
\(nP > 0\) |
yes |
Number of junction roads is positive. |
\(nS > 0\) |
yes |
Total number of hub locations is positive. |
\(M > 0\) |
yes |
Constraints¶
At most U new hubs (indices N..M-1) may be opened.
\[ \sum_{h=N}^{M-1} y_h \leq U \]All existing hubs (indices 0..N-1) must remain open.
\[ \sum_{h=0}^{N-1} y_h = N \]Demand from junction s to POI p can only be covered if at least one feasible open hub exists for the pair.
\[ z_{sp} \leq \sum_{h \in H} F_{shp} \, y_h \quad \forall s \in S, p \in P \]
Objective¶
Maximize the total commuter demand covered by the hub network.
Formulation b (valid)¶
See also
This formulation is sourced from Ferchtandiker2025 (variation id: inefficient).
Note
This is the disaggregate (inefficient) formulation.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
Number of existing hubs that must remain open (hubs 0..N-1) |
integer |
scalar |
|
Total number of hub locations (existing and potential new) |
integer |
scalar |
|
Number of Points of Interest (destinations) |
integer |
scalar |
|
Number of junction roads (commuter origins) |
integer |
scalar |
|
Commuter demand from junction s to POI p |
continuous |
|
|
Feasibility indicator: 1 iff junction-hub-POI triple is viable for Park and Bike use |
binary |
|
|
Maximum number of new hubs that can be opened |
integer |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
1 if hub h is opened, 0 otherwise |
binary |
|
|
1 if demand from junction s to POI p is assigned via hub h, 0 otherwise |
binary |
|
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
Commuter demand is non-negative. |
\(v_{sp} \geq 0 \quad \forall s \in S, p \in P\) |
yes |
The number of existing hubs does not exceed total hubs. |
\(N \leq M\) |
yes |
The maximum number of new hubs is non-negative. |
\(U \geq 0\) |
yes |
Number of Points of Interest is positive. |
\(nP > 0\) |
yes |
Number of junction roads is positive. |
\(nS > 0\) |
yes |
Total number of hub locations is positive. |
\(M > 0\) |
yes |
Constraints¶
At most U new hubs (indices N..M-1) may be opened.
\[ \sum_{h=N}^{M-1} y_h \leq U \]All existing hubs (indices 0..N-1) must remain open.
\[ \sum_{h=0}^{N-1} y_h = N \]Demand can only be assigned via hub h if that hub is open.
\[ x_{shp} \leq y_h \quad \forall s \in S, h \in H, p \in P \]Demand can only be assigned via a feasible hub.
\[ x_{shp} \leq F_{shp} \quad \forall s \in S, h \in H, p \in P \]Each (junction, POI) demand pair is assigned to at most one hub.
\[ \sum_{h \in H} x_{shp} \leq 1 \quad \forall s \in S, p \in P \]
Objective¶
Maximize the total commuter demand served via any open hub.