基于滿意度的投標(biāo)產(chǎn)生問題研究

文/鄭金諾 王浩青

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

1 引言

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

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

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

2.問題描述。

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

3.數(shù)學(xué)模型

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

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

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

圖1

3.3 模型建立

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

4.算法實(shí)現(xiàn)

4.1 禁忌搜索算法

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

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

4.3 確定參數(shù)

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

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

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

5.結(jié)論。

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