1.文章信息

題目：The prisoner transportation problem

作者：Jan Christiaens，Hatice ?alik，Tony Wauters，Reshma Chirayil Chandrasekharan， Greet Vanden Berghe

來源：European Journal of Operational Research

出版日期：17 January 2020

網(wǎng)址：https://doi.org/10.1016/j.ejor.2020.01.027

2.文章導(dǎo)讀

囚犯運(yùn)輸問題（Prisoner Transportation Problem，PTP）是常見車輛路徑問題的一種變體，涉及到用特殊的囚犯運(yùn)輸車，即用被細(xì)分為更小的單獨(dú)隔間的車輛，往返于醫(yī)院和法庭等目的地。從研究的角度來看，PTP包含兩個(gè)獨(dú)特的組成部分。第一個(gè)組成部分是同時(shí)服務(wù)，即在運(yùn)輸過程中，多個(gè)囚犯被安排同時(shí)上下車而不是依次上下車，這與大多數(shù)車輛路徑問題的標(biāo)準(zhǔn)做法不同。第二個(gè)組成部分涉及乘客之間的沖突，這可能發(fā)生在車廂或車輛層面。車廂沖突表示兩個(gè)囚犯不能同時(shí)占用同一個(gè)車廂，即被安排在不同車廂，而車輛沖突表示他們不能用同一輛車運(yùn)送。

3.摘要

在監(jiān)禁期間，囚犯經(jīng)常需要交通工具參與醫(yī)院預(yù)約、出庭和家屬探訪等服務(wù)，為滿足囚犯運(yùn)輸過程中所有安全和時(shí)間相關(guān)的限制，同時(shí)避免囚犯之間的沖突，囚犯需要由高度保護(hù)的車輛、司機(jī)和保安組成的龐大車隊(duì)運(yùn)輸，這無疑會消耗大量資源，PTP特定的組成部分(乘客間沖突和同時(shí)服務(wù))也帶來了相當(dāng)大的計(jì)算挑戰(zhàn)。雖然囚犯運(yùn)輸問題(PTP)與車輛路徑相似，但用于車輛路徑的通用軟件系統(tǒng)并不能解決與PTP相關(guān)的復(fù)雜問題，所以需要一個(gè)專門的決策支持系統(tǒng)來支持人力規(guī)劃者和降低業(yè)務(wù)成本。本文提出的啟發(fā)式算法提供了充分解決PTP的所有必要組件，并為新的公共實(shí)例集設(shè)置了初始基準(zhǔn)。

4.主要內(nèi)容

囚犯運(yùn)輸問題雖然在之前的運(yùn)籌學(xué)文獻(xiàn)中偶爾提到過，但本論文是第一次正式介紹。從本質(zhì)上說，這個(gè)問題是撥號乘車問題（dial-a-ride problem, DARP）。 DARP即多乘客拼車的車輛調(diào)度問題，是為司機(jī)規(guī)劃路線來完成由n個(gè)乘客發(fā)出的運(yùn)送請求，使得車輛能夠容納盡可能多的用戶，進(jìn)而最小化總行駛距離的問題。在這個(gè)過程中需要滿足時(shí)間窗、用戶最大行駛時(shí)間和車輛最大路線時(shí)長等約束。

囚犯運(yùn)輸問題的網(wǎng)絡(luò)示意圖如下所示，其中U表示倉庫節(jié)點(diǎn)的集合，包含U1和U2。U1表示作為車輛起始倉庫的原始倉庫集，即未接到囚犯前所有車輛容納處，U2表示作為車輛起始倉庫的副本，即結(jié)束倉庫，在接送完囚犯后車輛返回處。I=IP∪ID表示服務(wù)副節(jié)點(diǎn)集，即囚犯從上車至下車的過程，IP表示拾取節(jié)點(diǎn)，ID表示交付節(jié)點(diǎn)。

文章提出了PTP問題的一般模型，這個(gè)問題的目標(biāo)是在避免囚犯車廂和車輛沖突的基礎(chǔ)上，對每個(gè)節(jié)點(diǎn)加以時(shí)間限制，為所有的囚犯進(jìn)行同時(shí)服務(wù)，從而最大限度地減少車輛花費(fèi)的總時(shí)間。并將其應(yīng)用于PTP的幾種變體：有異質(zhì)車隊(duì)和乘用車兼容性限制的模型—某些乘客只能由車輛的某個(gè)子集運(yùn)送；目標(biāo)函數(shù)為最小化總路徑成本的模型—對一系列客戶需求點(diǎn)設(shè)計(jì)適當(dāng)路線，使得路徑成本最??；無同時(shí)服務(wù)模型—對任何一對乘客都不能進(jìn)行同時(shí)服務(wù)；無乘客沖突模型—不考慮乘客沖突，乘客可以安排在同一車廂或同一車輛。

PTP被分解為一個(gè)主問題和一個(gè)子問題。主問題被建模為具有同時(shí)服務(wù)的多車場撥號乘車問題，子問題為防止乘客間沖突。

在子問題中，介紹了一種貪婪啟發(fā)式算法，用于將囚犯分配到隔間，并舉例說明了在運(yùn)送四名囚犯時(shí)在六個(gè)過境點(diǎn)停留的行程。如下圖，圖2(a)虛線箭頭表示行程中轉(zhuǎn)站和囚犯運(yùn)輸a、b、c和d的順序，圖2(b)表示車輛在整個(gè)行程中的占用情況，該案例詳細(xì)描述了囚犯的上下車順序以及在車輛上旅行時(shí)長，明確標(biāo)識出囚犯之間的沖突，通過旅行時(shí)長安排和沖突避免，從而得到分配囚犯的解決方案。

圖3(a)顯示了具有兩個(gè)車廂的車輛，圖3(b)中，雖然囚犯b和d可能不共享同一隔間，但鑒于這兩個(gè)囚犯在車輛中的存在在時(shí)間上不重疊，這一邊緣是不相關(guān)的。因此，可以從圖中去除這條邊，得到圖3(c)。為了找到一個(gè)可行的囚犯分配，可以考慮一個(gè)圖著色問題，其中單個(gè)顏色分配的數(shù)量與每個(gè)中轉(zhuǎn)點(diǎn)的隔間容量相關(guān)聯(lián)。圖3(d)提供了一個(gè)可行的分配:囚犯a和c被分配到2號牢房，囚犯b和d被分配到1號牢房。請注意，雖然1號車廂的顏色被使用超過其相應(yīng)的容量，但它從來沒有超過這個(gè)容量在任何單一的過境點(diǎn)，如圖4所示。

在主問題中，考慮到了時(shí)間限制，囚犯上下車服務(wù)時(shí)間必須在其時(shí)間窗口內(nèi)完成，除時(shí)間窗約束外，最短行程時(shí)間也不得超過最長行程時(shí)間。主問題中還考慮到同時(shí)服務(wù)，即合并服務(wù)時(shí)間，將單個(gè)中轉(zhuǎn)點(diǎn)執(zhí)行的服務(wù)a和服務(wù)b合并到服務(wù)m中，該服務(wù)m代表兩個(gè)服務(wù)的最短可行執(zhí)行時(shí)間。如下圖，相對于中轉(zhuǎn)點(diǎn)花費(fèi)的總時(shí)間，合并后的服務(wù)時(shí)間被大大減短。通過利用時(shí)間限制來實(shí)現(xiàn)囚犯的同時(shí)服務(wù)，最終構(gòu)建可行的出行方案。

5.結(jié)論

本文介紹的囚犯運(yùn)輸問題（PTP）其建模困難主要與乘客間沖突和同時(shí)服務(wù)的存在有關(guān)，這兩個(gè)復(fù)雜的約束以前沒有模型，因此本文引入混合整數(shù)規(guī)劃模型來進(jìn)行PTP研究。由于混合整數(shù)規(guī)劃模型無法在合理的時(shí)間解決實(shí)際實(shí)例，本文引入啟發(fā)式方法來解決實(shí)際生成的大規(guī)模情況。將PTP問題分解為主問題和子問題，主問題中建立了混合整數(shù)非線性規(guī)劃模型，在模型中考慮了時(shí)間窗口、最大行駛時(shí)間、最大路線時(shí)長等時(shí)間約束，建立起合并服務(wù)時(shí)間及其關(guān)聯(lián)的時(shí)間窗口約束方程，在實(shí)現(xiàn)同時(shí)服務(wù)的基礎(chǔ)上，減少囚犯出行車輛行駛時(shí)長，從而使得所有車輛總行駛成本更??；子問題中引入了貪婪啟發(fā)式算法，有效地將囚犯分配到車廂和車輛，從而構(gòu)造出可行的囚犯出行方案。

6.展望

本文提供了一組實(shí)例，并提供了應(yīng)用基于局部搜索的方法獲得的初始基準(zhǔn)，以促進(jìn)對PTP的進(jìn)一步研究。本文所介紹的數(shù)學(xué)公式為后續(xù)的PTP研究奠定了必要的堅(jiān)實(shí)基礎(chǔ)，未來可能的研究方向包括建立進(jìn)一步的理論見解以及改進(jìn)解決方案的實(shí)用算法。

作者 |吳香璠 隋朝陽

責(zé)編 | 何洋洋

審核 | 徐小峰