The 21st Behavior Modeling in Transportation Networks
Sep. 24, 2022

A structured programming method
for matching heterogeneous demandin mixed freight and passenger network

D1 Fuga Mayuzumi
Behavior in Networks Laboratory (UTokyo)
mayuzumi@bin.t.u-tokyo.ac.jp

2Introduction
Mixed Passenger-and-Freight Delivery§ Matching heterogeneous demands ofpassengers and freight can be efficientby sharing temporally vacant slots

Michinoeki (Roadside Station) @Tsukechi town in Nakatsugawa city

Requirements for Demand Transportation① Trade-off relationship between fairness and efficiency② Heterogeneity in trip-patterns and usage time
③ Sudden cancels/requests in the middle of the routes② Heterogeneity① Policy trade-off# TripsMaximizing #users③ Robustness
Sudden cancel

Freight
Perishable
Delivery

Passengers

Reservation

Commutegoal

Trade-off
Sudden request

Minimizing travel cost
Time ZonestartPrevious Research3

Research on Mixed Passenger-and-Freight Delivery
SARP

Li et al.(2014)

Share-a-Ride Problem

PDP-FSL

Ghilas et al.(2013)

Pick-up and Delivery Problem
with Fixed Scheduled Lines§ First assigns passengers to vehicles,
and then utilizes the vacant slots for freight§ Represents mixed
passenger-and-freightsituation by NW setting▶ Heterogeneity in space-time prism constraints was not fully considered▶ Interaction between different demands was not analyzed

Previous Research4

Dynamic Dial-a-ride problem (DARP)Jaw et al.(1986) … Sequential insertion method: benchmark§ Online-algorithm for assignment of riders to drivers§ Minimize the difference from pre-determined matching▶ Algorithm is not supposed to be real-time
Tsubouchi et al.(2009)§ Improve Jaw et al.(1986) to make the algorithm real-time§ Completely separating riders’ assignment and scheduling for computation ease

▶ Assignment and scheduling are myopic▶ Changing the pre-determined routes is not allowed: not flexible

Requirements for algorithm

5

Based on the previous studies, our motivation for developing scheduling algorithm
for mixed passenger-and-freight vehicle is:

1. Achieving real-time performance for recalculation of scheduling vehicles
2. Incorporating the method to handle and analyze the heterogeneity inindividual requests and interaction among them

Our approach
1. Indexing method for flexibly recalculating feasible routes
2. Enumeration method explicitly handle individual demandMapping of the research
Recall back the lecture from Prof. Teodor yesterday…

today’s presentation corresponds to Execution part of city logistics

6

Framework

7

Motivating example

Feasible routes of passenger
At period 𝑡,

requests the driver to arrive at Node 3 within 3 steps from Node 1

Blue lines are the routes with minimum total travel distanceis to be at Node 1 or Node 3 at next time step

Framework

8

Motivating example

Feasible routes of freight
Suppose thatAt period 𝑡 + 1,

requests to arrive at Node 3 within 2 steps from Node 2The operator must recalculate the routes to pick-up the freight request

Framework

9Motivating example

To satisfy the request of, the operator must recalculate within one time step

Real-time processing of en-route requests is needed for efficient operation

10

Framework
Sequential Enumeration and Indexing Method

Our idea§ Preserving the pre-determined feasible paths as indexes which was not selected§ Utilizing the indexes to select alternative routes to satisfy new requests>>> faster than newly calculating the feasible routes from nothing
Enumeration and indexing

ExtractionIntractability of routes enumeration
The number of feasible routes increases rapidly as the number of
selective choices increases : combinatorial explosion
Example in the grid network# feasible routes

11Sequential Enumeration and Indexing 12
ZDD: a fast enumeration and indexing method§ Zero-suppressed binary Decision Diagrams§ Exact solution to the shortest path problem§ Explicitly representing the space-time prism constraints of individual demand[Example] Some agent at Node 1 needs to arrive at Node 2 within two time-steps(a) Feasible Routes(b) The binary decision tree representation

Concise route representation by ZDD 13
With two contraction rules for nodes irrelevant to the combination set :① Elimination of redundant nodes② Sharing equivalent nodes

ZDD enumerates and indexes the feasible routes concisely(b) The binary decision tree representation(c) ZDD representation

Outstanding effect on sparse combination sets

Contraction Rule: Elimination① Elimination of redundant nodes: deleting and skipping the node
when the destination of the 1-branch is 0-leaf14

Contraction Rule: Sharing② Sharing equivalent nodes: share the nodes whose names are the same andthe destination of 1-branch and 0-branch is the same15

Set operation among ZDDs

16

Matching multiple requests with set operation§ ZDDs are capable of set operation among them
§ Enumerate individual feasible routes, and then join them sequentially

Matching criteria matter for improving
success rate of matching or mitigating calculation cost17

Set operation among ZDDsMatching multiple requests with set operation§ ZDDs are capable of set operation among them
§ We can get the combination of decision variables whether the link intime-extended network is selected concisely by ZDD𝑒$,&,' ∈ 0,1 )𝑖, 𝑗: Nodes 𝑡: time-step

𝑇: Whole period§ If we think of matching multiple requests, combination of decisionvariables has an additional index representing the agent(𝑒$,&,'Product set of𝑛: agent index%
𝑒!,#,$&⊔ 𝑒!,#,$

gives feasible routes
satisfying multiple requests§ Calculation cost of joining operation among multiple ZDDs are basedon the number of nodes in each ZDD, not on the # feasible routesZDDs are thought to be effective for matching problem

Matching based on marginal contribution

18Marginal Contribution§ Marginal contribution in cooperative games quantify the influence of aparticipator to the coalition (set of agents)§ The assignment maximizing the marginal contributions of all agents iscalled Shapley assignment, and the problem finding such assignment iscalled coalition structure generation (CSG) problem.
Coalition 𝑆: Combination of passengers and freight
Coalition Value 𝑣(𝑆): Score of coalition(characteristic function)
𝑇𝑇𝐷' : Total travel distance achieved by Coalition SMarginal contribution𝑣 𝑆∪ 𝑖|𝑆|𝑣 𝑆 =𝑇𝑇𝐷*… Difference between the score with/without 𝑖

𝑆∪ 𝑖|𝑆|−𝑣 𝑆 =−𝑇𝑇𝐷*∪ ,𝑇𝑇𝐷*𝑖 denotes a new participator to the coalition 𝑆

Setting for matching simulation

19Target Network and Policy of Mixed Passenger-and-Freight§ Passenger or freight requests at each node on NW§ at an arbitrary discretized time-step from 𝑡 = 0 to 𝑡 = 9§ toward three vehicles with initial position at Node 1,5,6* each link takes 1 time-step§ Operator matches the requests sequentially andcalculate the optimum routes of all agents in two policies① TD-model
Matching with minimizing total travel distance② MC-model
Matching with maximizing marginal contribution

Heterogeneity in passenger and freight§ Passengers and freight are distinguished by their tolerance to the additional
travel time due to accepting the succeeding requests.
<= We define the tolerance to detouring as a detour ratio§ Detour ratio is set to be zero for passenger, and positive for freight※ The system would like the preceding users to change their routes with equal travel
distance or detour to some extent for succeeding requestsFlowchart of matching algorithm

20Eq.(2) … Objective function of TD-modelEq.(3) … Objective function of MC-modelEq.(4) … Decision variables
𝛿!,# : whether vehicle j accepts user i’s request
𝜂!,$,% : whether user i flows into link e at time t

Eq.(5) … Capacity constraint of each vehicle
Eq.(6) … Flow conservation ruleSimulation Results
Comparison of matching success rate in MC-model/TD-model§ The result below is the average of 30 random OD sets in the cases
where the detour ratio is 0.1 and 0.2 for five proportion patterns ofpassenger to freightmixed(“MC-model” – “TD-model”)

More users were accepted in the MC-modelin all patterns where passengers and freight is mixed
This is because overlapping of users’ routes are favoredin matching with MC-model based on the coalition value

21

Simulation Results

22Comparison of matching success rate in MC-model/TD-model§ The result below is the average of 30 random OD sets in the cases
where proportion pattern is 3 passengers and 4 freight(“MC-model” – “TD-model”)

Contrary to expectations, however, Ave. Offset did not
get bigger as the detour ratio increased.
This result did not conclude that the detour ratio was
not so useful, for the average coalition value did notdecrease according to the detour ratio.

Example of matching result
Matching with TD-model … Total travel distance: 30# User: 2# User: 2# User: 2

Matching with MC-model … Total travel distance: 26# User: 1# User: 1# User: 423

数値計算設定
Summary24

1. A sequential enumeration and indexing algorithm was constructedusing ZDD, satisfying individual heterogeneous space-time prism
constraints of passengers and freight.
2. ZDD recalculation of alternative routes was executed within seconds inthe case of 3*3 grid network with ten time-steps.
3. Marginal contribution was employed as an assignment (matching)criterion, mitigating the system load and thus achieving robustness tothe uncertain future requests.
Future worksa) Construct surrogate model or multi-scale model for large-scalecomputation in actual network.
b) (Demand side) Suppose some behavioral assumptions for requests tobe generated using behavior data.
c) (Supply side) Suppose that the availability of the logistics facility orgoods changes based on the behavior historyd) Incentive design for detouringThank you for listening JReferences251) Ghilas, V., Demir, E., and Van Woensel, T.: Integrating passenger and freighttransportation: Model formulation and insights, BETA publicatie: Working
papers, Vol.441, 2013.
2) Li, B., Krushinsky, D., Reijers, H. A., and Van Woensel, T.: The share-a-ride
problem: People and parcels sharing taxis, European Journal of Operational
Research, Vol.238, No.1, pp.31–40, 2014.
3) Jaw, Jang-Jei, et al.: A heuristic algorithm for the multi-vehicle advance request
dial-a-ride problem with time windows, Transportation Research Part B:
Methodological 20.3 (1986): 243-257.
4) O. B. Madsen, H. F. Ravn, and J. M. Rygaard, “A heuristic algorithm for a diala-ride problem with time windows, multiple capacities, and multiple objectives,”
Annals of operations Research, vol. 60, no. 1, pp. 193–208, 1995.
5) Tsubouchi, K., Hiekata, K., and Yamato, H.: Scheduling algorithm for ondemand bus system, Vol. 10, pp. 189 – 194, 05 2009.
6) Minato, S.: Zero-suppressed bdds for set manipulation in combinatorial
problems, pp. 272–277, 1993.
7) Hayakawa, K. and Hato, E.: Dynamic traffic resources allocation under elastic
demand of users with space-time prism constraints, arXiv preprint
arXiv:1806.10719, 2018.