計程車共乘問題（The shared-taxi problem）

Hadi Hosni, Joe Naoum-Sawaya, Hassan Artail.(2014). The shared-taxi problem: Formulation and solution methods.Transportation Research Part B,70,303–318.

日常整理paper，共乘問題，對象均為乘客。特點：①在model部分，passengers分為兩類，onboard passengers以及seekers。②在解法上，運用拉格朗日分解法，把問題分解為更小的子問題，提高效率。③啟發式，incremental cost heuristic（ICH）。

交通運輸方面的低效率，導致一些經濟和環境問題，比如交通擁塞，交通污染嚴重。隨著燃料成本的上漲，共乘成為一種常見的交通方式。共乘具有的的優點：①最小化taxi的空位率；②可以減少taxi公司的營運成本；③對於乘客而言票價更優惠；④減少道路擁堵；⑤最小化交通對於環境造成的影響。共乘，目的最小化車輛空位的數量，因此來減少車輛的需求數。

回顧之前相關共乘文獻，發現主要關注於兩點，開發高效的 car pooling 系統，以及優化公共運輸系統。但，共乘問題也存在著很大的挑戰，比如，共乘的服務定價問題，共乘的乘客匹配問題。

簡述一下共乘問題，共乘問題都為多車動態DARP問題（multi-vehicle dynamic Dial-A-Ride Problem）。首先，taxi目前已經服務的乘客稱為onboard passengers，發布請求準備搭乘車的乘客稱為 seekers。taxi-seekers 發布共乘請求，包括乘客的上車地點以及目的地，以及設置相關的時間，預計最早的taxi達到時間，最遲的下車時間，最大的乘車時間。共乘問題的目的為，確定最佳的乘客指派，把未接受服務的乘客指派給taxi，同時最優化每台taxi的route。

該篇文章有以下幾點貢獻：a.提出一個混合整數規劃模型，以及總結了多台車的動態DARP問題。b. 提出拉格朗日分解啟發式演算法，把複雜的問題分解為更好求解的子問題。c.為了減少計算的困難度，再提出一個incremental cost heuristic（ICH）啟發式。

二、literature review

主要回顧了與DARP相關的文獻，好想偷懶GG，就讓我偷懶吧。

1. Desrosiers et al., 1995;Desaulniers et al., 2002

The DARP is a generalization of vehicle routing problems, like the Pick-up and Delivery Vehicle Routing Problem and the Vehicle Routing Problem with Time Windows.

2. Psaraftis (1980) and Psaraftis (1983)

A dynamic programming approach, in which the objective function takes into consideration both cost minimization and customer dissatisfaction minimization.

3. Attanasio et al. (2004)

proposes parallel tabu search heuristics for the dynamic DARP where an initial

static solution is first achieved and then the new passenger requests are inserted into the solution as they arrive.

4. Cordeau (2006)

A branch-and-cut algorithm that uses valid inequalities that are derived from the dial-a-ride.

以下省略 n 多字，以後再端正態度。

三、Problem description

（一）問題假設

1.所有passengers從相應的pickup locations 上車，到達相應的dropoff locations 下車。

2.潛在的passengers 可能被拒絕，如果服務改乘客，無利可圖，則改乘客的請求將被拒絕。

3.時間上，pickup和dropoff 都要符合特定的時間窗，passenger的乘坐時間ride time不能超 過最大的ride time。

4.每台車上的passengers 的數量不能超過車輛的最大載客數量。

5.passengers 可以在任意時間點，進入或出去該系統。

6.假設每台車輛在不同的locations ,有不同的capacities ,都有onboard passengers.

（二）數學model

1. Objective

目標是在不違背pickup和dropoff的時間窗，以及最大ride time下，求最大化總利潤。

2.Model Notation

先定義參數和決策變數，這些都是引用paper中的。