A solution methodology for carpooling systems based on double auctions and cooperative coevolutionary particle swarms

P

the number of different passengers in the carpooling system; the set of all passengers is denoted by {1, 2, 3,....P}.

p

the index of a passenger, where p ∈{1, 2, 3,....P}.

K

the number of all pick-up and drop-off locations of passengers. Without loss of generality, it is assumed that all the pick-up and drop-off locations of passengers are distinct. In this case, there are P pick-up locations and P drop-off locations and K = 2P.

k

the index of a pick-up location or a drop-off location, where k ∈{1, 2,...,K}.

L _k

the k -th location, where k ∈{1, 2,...,K}.

D

the number of drivers in the carpooling system; the set of all drivers is {1, 2, 3,....,D}.

d

the index of a driver, where d ∈{1, 2, 3,....,D}.

J _d

the number of bids placed by driver d, where d ∈{1, 2,...,D}.

j

the j − th bid submitted by driver d, where d ∈{1, 2,...,D} and j ∈{1, 2,...,J_d}.

Π

a route, which consists a sequence of locations.

π _d

the original route taken by driver d when driver d travels alone.

π_dj(Lo_d, Le_d)

the route corresponding to the j − th bid submitted by driver d, where d ∈{1, 2,...,D} and j ∈{1, 2,...,J_d}, Lo_d and Le_d denote the origin and destination of route π_dj, respectively. π_dj(Lo_d, Le_d) is abbreviated as π_dj whenever its is clear from the context. π_dj consists of a sequence of locations \(L_{1} ,L_{2} ,...,L_{\left | {M_{dj} } \right |} \).

k _{d j m}

the m − th location visited by route π_dj, \(m\in M_{dj} =\{1,2,...,\left | {\pi _{dj} } \right |\}\)

Π_d

the set of all routes submitted by driver d, where d ∈{1, 2,...,D}, \({\Pi }_{d} =\{\pi _{dj} \left | {j\in \{1,2,...,J_{d} \}\}} \right .\).

a _d

the number of available seats (capacity of the car) provided by driver d, where d ∈{1, 2, 3,....,D}.

τ _{d j}

\(\tau _{dj} = \frac {dist(\pi _{dj} (Lo_{d} ,Le_{d} ))}{dist(\pi _{d} (Lo_{d} ,Le_{d} ))}:\) the detour ratio of route π_dj.

\(\bar {{\tau }}_{d} \)

the maximum detour ratio specified by driver d .

R _d

\(R_{d} = (Lo_{d} ,Le_{d} ,{\omega _{d}^{e}} ,{\omega _{d}^{l}} ,a_{d} ,\bar {{\tau }}_{d} ):\) the requirements of driver d , where \(Lo_{d} ,Le_{d} ,{\omega _{d}^{e}} ,{\omega _{d}^{l}} \), a_d and \(\bar {{\tau }}_{d} \) denote the origin, destination, earliest departure time, latest arrival time, quantity of available seats and maximum detour ratio specified by driver d, respectively.

τ _{p d}

estimated detour ratio \(\tau _{pd} =\frac {\gamma (p,d)}{dist(\pi (Lo_{dj} ,Le_{dj} ))}\), where γ(p, d) = dist(Π(Lo_d, Lo_p)) + dist(Π(Lo_p, Le_p)) + dist(Π(Le_p, Le_d))

R _p

\(R_{p} = (Lo_{p} ,Le_{p} ,{\omega _{p}^{e}} ,{\omega _{p}^{l}} ,n_{p} ):\) the request of passenger p, where \(Lo_{p} ,Le_{p} ,{\omega _{p}^{e}} ,{\omega _{p}^{l}} \) and n_p denote the origin, destination, earliest departure time, latest arrival time specified by passenger p and the number of passengers to be transported, respectively, and p ∈P.

\(t_{p}^{dep} \)

the time passenger p is picked up at Lo_p.

\(t_{p}^{arr} \)

the time passenger p is dropped of at Le_p.

\(t_{d}^{dep} \)

the time driver d departs at Lo_d.

\(t_{d}^{arr} \)

the time driver d arrives at Le_d.

B _d

the set of passengers \(^{\prime }\)a_d -smallest estimated detour ratio (τ_pd) requests for each driver d ∈{1, 2,...,D}; \(B_{d} =\{R_{p} \left | {p\in \{1,2,3,....P\},\tau _{pd} } \right .\) is a_d -smallest }

c _{d j}

the cost for transporting the bundle of passengers in the j − th bid submitted by driver d.

o _d

the travel cost for taking the route π_d by driver d without transporting any passengers. That is, o_d is the cost that driver d travels alone.

\(q_{djk}^{1} \)

a nonnegative integer that denotes the quantity of seats offered to pick up passengers at location k in the j − th bid submitted by driver d ; \(q_{djk}^{1} =\) 0 if location k is not visited by π_dj.

\(q_{djk}^{2} \)

a nonnegative integer that denotes the quantity of seats released due to dropping passengers at location k in the j − th bid submitted by driver d; \(q_{djk}^{2} =\) 0 if location k is not visited by π_dj.

\(b_{dj}^{D} \)

\(b_{dj}^{D} = (q_{dj1}^{1} ,q_{dj2}^{1} ,...,q_{djk}^{1} ,...,q_{djP}^{1} ,q_{dj1}^{2} ,q_{dj2}^{2} ,...,q_{djk}^{2} ,...,q_{djP}^{2} ,\pi _{dj} ,c_{dj} ,a_{d} ): \) a vector generated based on R_d to represent the j − th bid submitted by driver d. The j − th bid \( b_{dj}^{D} \) is actually an offer to transport passengers specified by \( q_{djk}^{1} \) and \( q_{djk}^{2} \) for each k ∈{1, 2, 3,....,P} at the cost c_dj with capacity a_d by following route π_dj.

π_p(Lo_p, Le_p)

the original route from Lo_p to Le_p that will be taken when passenger p travels alone. π_p(Lo_p, Le_p) will be abbreviated as π_p whenever it is clear from the context.

n _p

the number of passengers to be transported in the bid of passenger p.

\(s_{pk}^{1} \)

the number of seats requested in the bid of passenger p to pick up passengers at pick-up location L_k, where k ∈{1, 2, 3,....,P}.

\(s_{pk}^{2} \)

the number of seats to be released from in the bid of passenger p due to dropping passengers at location L_{P + k}, where k ∈{1, 2, 3,....,P}.

f _p

the price of the bid submitted by passenger p based on the original travel cost of passenger p when he/she travels alone.

\({b_{p}^{P}} \)

\({b_{p}^{P}} = (s_{p1}^{1} ,s_{p2}^{1} ,s_{p3}^{1} ,...,s_{pP}^{1} ,s_{p1}^{2} ,s_{p2}^{2} ,s_{p3}^{2} ,...,s_{pP}^{2} ,f_{p}):\) a vector generated based on R_p to represent the bid submitted by passenger p. The bid \( {b_{p}^{P}} \) is an offer to pay f_p for transporting passengers.

Γ_dj

the set of passengers delivered in the j -th bid submitted by driver d

x _{d j}

the variable to indicate the j − th bid placed by driver d is a winning bid (x_dj = 1) or not (x_dj = 0).

y _p

the variable to indicate the bid placed by passenger p is a winning bid (y_p = 1) or not (y_p = 0).

α

cost savings allocation coefficient for carpooling information provider.

e _{d j k}

a nonnegative integer that denotes the quantity of empty seats available after dropping and picking up passenger at location k in the j − th bid submitted by driver d.