文/鄭金諾 王浩青

在物流運輸服務中，托運人除了考慮配送成本以外，還會考慮客戶的滿意度，如交貨時間。準時的交貨可以有效地給客戶提供更好的服務。承運人在投標過程中也要根據(jù)托運人的需求來進行投標選擇。本文研究了通過組合拍賣實現(xiàn)的協(xié)同運輸中承運人的投標產(chǎn)生問題并且考慮客戶的滿意度，使用禁忌搜索算法對所提出的模型進行了驗證。

1 引言

隨著我國公路運輸服務的迅速發(fā)展，越來越多的企業(yè)提供在線服務，并承諾在數(shù)小時內(nèi)送達，以方便城市地區(qū)的人們的生活。這種環(huán)境下給承運人帶來了重大的挑戰(zhàn)，承運人必須做出明智的決策，才能在競爭如此激烈的環(huán)境下生存。對于托運人，承運人的客戶，除了最大限度地降低運輸成本以滿足他們的要求，他們還對減少訂單的交貨提前時間感興趣。在許多情況下，雖然成本是評估承運人提交的投標的一個重要屬性，但托運人在評估投標時也會關注每個承運人的服務質(zhì)量，客戶會考慮貨物到達的時間，從而影響客戶的滿意度。

組合拍賣（CA）是多線路拍賣的一種方式，托運人作為拍賣人，發(fā)放在幾個出發(fā)地和目的地之間運輸服務的需求，承運人作為投標人，通過提交托運人發(fā)布的運輸合同的投標來進行競爭。本文主要解決在組合拍賣問題中包含的投標生成問題（bid generation problem，BGP）。投標生成問題必須由參與拍賣的每個承運人來解決。允許組合投標時，包括確定要投標的拍賣合同的子集和要求在每次投標中送達所有合同的價格。

組合拍賣問題已經(jīng)有許多國內(nèi)外學者進行研究，Rekik[1]等人（2017）提出了基于路徑的CA中BGP的公式，該公式具有同質(zhì)車隊，并采用分支-價格-削減的方法求解。Ben Othmane[2]等人（2019）研究了BGP的一種變體，在這種變體中，承運人通過將可拍賣的合同與現(xiàn)有路線整合在一起來優(yōu)化運營。Triki[3]等人（2014）考慮了CA具有隨機清算價格的BGP。他們提出了一個概率優(yōu)化模型，集成了投標構建和定價問題，只允許產(chǎn)生一個組合投標。李軍[4]等人針對運輸服務采購的多輪組合拍賣問題，考慮承運人競價不確定特征，構建了上層最小化托運人成本和下層最大化承運人利潤的二層規(guī)劃模型。綜上所述，本文站在承運人的角度考慮組合拍賣的投標同時滿足客戶要求，提高滿意程度建立了以總成本最小，滿意度最大為目標的數(shù)學模型，結合Solomon算例并使用禁忌搜素算法進行仿真實驗對模型進行驗證。

2.問題描述。

由于承運人競爭隨物流環(huán)境的發(fā)展變得愈來愈激烈，承運人需要考慮更多投標因素。本文考慮了基于時間窗口的滿意度問題，當在預定的時間窗前后送達貨物時，會導致滿意度下降。從而降低承運人以后的拍賣效率。除了考慮滿意度的同時，承運人也要考慮自己的成本，如何在保證滿意度高的情況下，減少承運人成本是本文的目標。此外還引用了李倩[5]等設計的懲罰成本函數(shù)，未按約定時間送達貨物要支付懲罰金，這也算在承運人的總成本內(nèi)。假設如下：（1）承運人車隊車輛為同質(zhì)車輛并且裝載貨物不能超過車輛載重量；（2）已知送貨點位置及預定的時間窗；（3）每個送貨點僅由一輛車提供配送服務，且只能到達和出發(fā)一次，但每輛配送車可服務多個送貨點。

3.數(shù)學模型

3.1 參數(shù)設置。本文設置了一個有向圖G=(N，E)，其中N為所有節(jié)點的集合，包括所有收貨和交付節(jié)點以及承運人倉庫節(jié)點，E為邊集。節(jié)點集設置為N=（0，1，…，2n+1），n為請求數(shù)量，0和2n+1均為承運人倉庫節(jié)點。I為取貨點；j為交付點；H表示一組周期；K為車輛數(shù)量，本文承運人車隊為同質(zhì)車輛；Q為車輛容量，車輛不能超載；q表示取貨點需求量；tij表示從i點到j點的運輸時間；cij表示從i點到j點的運輸成本；所有請求的取貨點集設置為P，交付點設置為D；決策變量xijhk=1表示只有車輛k在周期h中訪問節(jié)點i之后直接訪問節(jié)點j，否則為0；yihk=1表示請求i由車輛k在周期h內(nèi)送達，否則為0；uihk為車輛k在周期h中到達節(jié)點i的時間。

3.2 引入滿意度函數(shù)

假設客戶預約服務時間為[ei，li]，如果在此時間窗內(nèi)進行配送，則fi（ti）=1。但是在實際運輸過程中會遇到外部環(huán)境影響等狀況，就會導致實際配送時間與預約的時間不符，導致滿意度會下降。假設[Ei，Li]分別表示客戶能接受的最早和最晚服務時間。若在[Ei，ei]或[li，Li]時間范圍內(nèi)進行配送，則客戶滿意度隨著與預約服務時間窗的時間差的增大而降低。若配送時間在[Ei，Li]范圍之外，fi（ti）=0。圖1為客戶滿意度隨時間窗變化情況。

圖1

3.3 模型建立

約束（3）確保車輛在一個周期到達某個點，必須在同一周期離開；約束(4)確保每輛車在一個周期離開承運人倉庫，必須在同一周期返回；約束（5）必須在同一周期內(nèi)使用相同車輛的取貨點之后訪問其交付點；約束（6）定義等待時間；約束（7）確保送貨時間在最大約束時間內(nèi)；約束（8）確保車輛不超載；約束（9）為各項決策變量。

4.算法實現(xiàn)

4.1 禁忌搜索算法

禁忌搜索（簡稱TS）最早是由Glover F.[6]于1986年提出，是一種改進的局部搜索算法。此算法的基本原理是：對某問題給定一個初始解和領域結構，在領域中通過一定規(guī)則確定若干候選解；若這些候選解的值的值好于當前的最優(yōu)解，則藐視準則被觸發(fā)，忽視禁忌狀態(tài)，用其替代當前解和最佳狀態(tài)，并納入禁忌表；若候選解均不好于最優(yōu)解，則從候選解中找出最優(yōu)，將其加入禁忌表中；如此不斷迭代上述過程，直至滿足停止準則。禁忌表是用來存放禁忌對象的表。它是禁忌搜索得以進行的基本前提。禁忌表本身是有容量限制的，它的大小對存放禁忌對象的個數(shù)有影響，會影響算法的性能，禁忌對象是指禁忌表中被禁的那些變化元素。禁忌長度指的是禁忌對象不能被選取的周期。禁忌搜素算法基本步驟如下：（1）給定算法參數(shù)，隨機產(chǎn)生初始解x，置禁忌表為空。（2）判斷算法終止條件是否滿足？若是，則結束算法并輸出優(yōu)化結果；否則，繼續(xù)以下步驟。（3）利用當前解的鄰域函數(shù)產(chǎn)生其所有（或若干）鄰域解，并從中確定若干候選解。（4）對候選解判斷特赦準則是否滿足？若成立，則用滿足特赦準則的最佳狀態(tài)y替代x成為新的當前解，即x=y，并用與y對應的禁忌對象替換最早進入禁忌表的禁忌對象，同時用y替換“best so far”狀態(tài)，然后轉(zhuǎn)步驟6；否則，繼續(xù)以下步驟。（5）判斷候選解對應的各對象的禁忌屬性，選擇候選解集中非禁忌對象對應的最佳狀態(tài)為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象元素。（6）轉(zhuǎn)步驟（2）。

4.2 實驗算例及測試環(huán)境本文采用基本的禁忌搜素算法和Solomon算例中的C208算例來驗證本文所提出模型的有效性。使用的軟件為matlab R2019a,設備為Intel(R)Core(TM)i7-6700HQ CPU@2.60GHz,8g內(nèi)存。

4.3 確定參數(shù)

設向量X、Y和K用于表示所提出問題中的每個解，向量X由所有取貨節(jié)點和交付節(jié)點組成，其大小為.向量Y的大小等于所有請求的數(shù)量，與請求相對應的向量Y的每個分量表示分配給服務請求的周期。K的每個分量對應一個請求，K的維數(shù)等于所有請求的數(shù)量。請求量與取貨點的量相同。

首先，從向量X的第一個分量到最后一個分量逐個選擇取貨和交付節(jié)點。在選擇取貨節(jié)點及其相應的請求之后，根據(jù)向量Y和向量K依次確定服務于請求的周期和車輛（路線）。當一個取貨節(jié)點在一段時間內(nèi)被分配給一條路線時，其成對的交付節(jié)點也被分配給同一時間段的同一條路線。如果在當前路線中插入請求導致不可行的解決方案，則將創(chuàng)建新路線，這意味著插入違反了時間窗口約束，或者由于車輛容量約束，當前路線無法滿足請求。一些算法參數(shù)設置為：禁忌長度：20；最大迭代次數(shù)：300；車輛負載：700；車輛成本：500；車輛單位距離運輸費用60元/km。送貨時間早于時間窗則罰款30元，晚于時間窗則罰款80元。

以總成本最小，滿意度最大為目標，最終得到最短距離946.4050km；使用車輛10輛；實驗中出現(xiàn)了違反時間窗范圍的情況，導致滿意度下降，滿意度為94%，總成本為62164.3元。

5.結論。

本文提出了一個考慮滿意度的投標生成問題，滿意度從時間窗入手，設定了時間周期，一個最早和最晚的時間期限。承運人要在預定的周期內(nèi)完成任務才能獲得更高的滿意度.同時還建立了一個數(shù)學模型，并使用了禁忌搜索算法來對模型進行檢驗。通過解決此問題，承運人可以確定在組合拍賣過程中服務哪些運輸請求，為承運人提供了更有力的競爭手段，此外，托運人也得到了決定競勝標的新標準。