Shared delivery route: each segment is charged to whoever needs it driven

Five stops share one road. Split the bill by distance and the nearest stop pays 6.29 for road only the far stops need; charge each segment to whoever needs it driven and it pays 4. The shares still add to the 110 bill.

Live result

Stop A pays 6.29 by distance and 4.00 by segments for the same road.

A4.00 segments6.29 distance
B6.50 segments9.43 distance
C26.50 segments28.29 distance
D31.50 segments31.43 distance
E41.50 segments34.57 distance
Pay more by distance3 of 5 stops
Largest excess versus aloneA, 11.4%

The segment shares add to 110.00; no stop pays more than its cost alone.

Givens

Try a road

Each gap starts at the previous stop; the first starts at the depot.

Stop 1
Name 1A
Gap Akm
Stop 2
Name 2B
Gap Bkm
Stop 3
Name 3C
Gap Ckm
Stop 4
Name 4D
Gap Dkm
Stop 5
Name 5E
Gap Ekm

Cost of a kilometre, one way: 1.00; Every amount on the page scales with it, so it is fixed here.

One road, two bills per stop

SegmentsDistanceAlone

The bars share one cost scale; each short tick shows what that stop would cost alone.

Every stop under both rules

Stop: A
From depot, km: 10
Alone: 20.00
Segments: 4.00
Distance: 6.29
Difference: 2.29

Stop: B
From depot, km: 15
Alone: 30.00
Segments: 6.50
Distance: 9.43
Difference: 2.93

Stop: C
From depot, km: 45
Alone: 90.00
Segments: 26.50
Distance: 28.29
Difference: 1.79

Stop: D
From depot, km: 50
Alone: 100.00
Segments: 31.50
Distance: 31.43
Difference: -0.07

Stop: E
From depot, km: 55
Alone: 110.00
Segments: 41.50
Distance: 34.57
Difference: -6.93

Stop	From depot, km	Alone	Segments	Distance	Difference
A	10	20.00	4.00	6.29	2.29
B	15	30.00	6.50	9.43	2.93
C	45	90.00	26.50	28.29	1.79
D	50	100.00	31.50	31.43	-0.07
E	55	110.00	41.50	34.57	-6.93

A positive difference means distance charges more; both rules divide the same bill before rounding.

Here is the maths

Two ways to divide the road

Add the gaps before a stop:

D_i=\sum_{k=1}^{i} g_k

where

D

is distance from the depot and

i

the stop's position and

g

a gap and

k

its segment's position.

A stop alone needs an outward and return trip:

C(i)=2cD_i

where

C

is its cost alone and

c

the cost per kilometre.

The whole run reaches the farthest stop and returns:

C(N)=2cD_n

where

N

is the set of stops and

n

its size.

Share each segment equally among the stops needing it:

x_i=\sum_{k=1}^{i}\frac{2c\,g_k}{n-k+1}

where

x

is a stop's segment share.

Distance instead divides the bill in proportion to each stop's distance:

y_i=C(N)\cdot\frac{D_i}{\sum_{j=1}^{n} D_j}

where

y

is its distance share and

j

a stop in the sum.

The segment shares exhaust the bill:

\sum_{i=1}^{n} x_i=C(N)

Each stays within its cost alone:

x_i\le C(i)

Subtract to see what distance adds:

e_i=y_i-x_i

where

e

is the extra charge under distance.

Why charge by segments

Average each stop's added cost over every joining order: that is its Shapley value, exactly its segment share here. Each segment is needed only by the stops at or beyond it. Charging those stops keeps the shares within their costs alone and accounts for the whole bill.

A worked example

The nearest stop needs only the first segment; the farther stops share it and pay for the rest.

With gaps of 10, 5, 30, 5 and 5 kilometres and a unit cost of 1, the bill is:
$C(N)=2\cdot 1\cdot 55=110$
All five stops share the first segment:
$x_1=\frac{2\cdot 1\cdot 10}{5}=4$
Four share the second:
$x_2=4+\frac{2\cdot 1\cdot 5}{4}=6.5$
Three share the third:
$x_3=6.5+\frac{2\cdot 1\cdot 30}{3}=26.5$
Two share the fourth:
$x_4=26.5+\frac{2\cdot 1\cdot 5}{2}=31.5$
Only the farthest needs the last:
$x_5=31.5+\frac{2\cdot 1\cdot 5}{1}=41.5$
Their shares recover the bill:
$4+6.5+26.5+31.5+41.5=110$
The distances from the depot sum to:
$\sum_j D_j=10+15+45+50+55=175$
Distance charges the nearest stop:
$y_1=110\cdot\frac{10}{175}=\frac{44}{7}$
That is 6.29, against 4 by segments.
It charges the farthest:
$y_5=110\cdot\frac{55}{175}=\frac{242}{7}$
That is 34.57, against 41.5 by segments.
The nearest stop's extra charge is:
$e_1=\frac{44}{7}-4=\frac{16}{7}$
That is 2.29 to the cent.
Its cost alone is:
$C(1)=2\cdot 1\cdot 10=20$
The excess is 11.4 per cent of that cost, the largest proportion here.

Show the full maths

Every joining order gives the segment rule

A group needs only the road to its farthest stop and back; an empty group costs nothing:

C(S)=2c\max_{j\in S}D_j\qquad C(\varnothing)=0

\begin{gathered}C(S)=2c\max_{j\in S}D_j \\ C(\varnothing)=0\end{gathered}

where

S

is a group of stops.

For each joining order, charge a stop the extra road cost when it joins, then average over all orders:

\phi_i=\frac{1}{n!}\sum_{\pi\in\Pi(N)}\left[C\!\left(P_i^\pi\cup\{i\}\right)-C\!\left(P_i^\pi\right)\right]

where

\phi_i

is its Shapley share and

\pi

a joining order and

\Pi(N)

the set of all joining orders and

P_i^\pi

the stops before it in that order.

The stops needing a segment are exactly those at it or farther along the road:

N_k=\{k,k+1,\ldots,n\}\qquad |N_k|=n-k+1

\begin{gathered}N_k=\{k,k+1,\ldots,n\} \\ |N_k|=n-k+1\end{gathered}

where

N_k

is that set of stops.

Only the first of those stops to join adds the segment to the bill. Each is equally likely to arrive first, regardless of the order of stops nearer the depot:

\Pr\!\left(P_i^\pi\cap N_k=\varnothing\right)=\frac{1}{n-k+1}\qquad i\ge k

\begin{gathered}\Pr\!\left(P_i^\pi\cap N_k=\varnothing\right)=\frac{1}{n-k+1} \\ i\ge k\end{gathered}

A stop never adds a segment beyond itself. For every segment it needs, multiply its full return cost by that first arrival chance, then add the averages:

\phi_i=\sum_{k=1}^{i}2c\,g_k\,\frac{1}{n-k+1}=x_i

This is exactly the segment rule.

For the five stops in the worked example, the number of equally weighted orders is:

5!=120

Summing each stop’s added costs over those orders and dividing by their count gives:

\begin{gathered}(\phi_1,\ldots,\phi_5)=\frac{1}{120}(480,780,3180,3780,4980)\\(\phi_1,\ldots,\phi_5)=(4,6.5,26.5,31.5,41.5)\end{gathered}

The average therefore recovers all five worked shares, not just the total bill.

What each control can move

The gaps and stop count move the shares and which stops pay more by distance; a third gap of 20 kilometres removes the fourth stop from that set.

The fixed kilometre cost scales every amount proportionally:

e_i(\lambda c)=\lambda\, e_i(c)

where

\lambda

is the scale factor.

What this does not model

One road, one return trip; no route choice or branching network.

No tariffs, capacity limits or choice of stops to serve.

No travel time, waiting or driver hours.

Source

Hervé Moulin, Fair Division and Collective Welfare, explains shared road costs, the Shapley value and the cost alone bound.

Scale: Amounts and distances shown to 2 decimals
Basis: Typed gaps in road order; cost per kilometre fixed at 1, one way
Model version: 1.0.0

The whole record prints. Your browser can save it as a PDF instead of printing it.

This compares two cost sharing rules for the road you describe. It sets no tariff and chooses neither the route nor the stops to serve.

Givens

One road, two bills per stop

Every stop under both rules

Here is the maths

Two ways to divide the road

Why charge by segments

A worked example

Every joining order gives the segment rule

What each control can move

What this does not model

Source

Related