基于改進(jìn)遺傳算法的旅客列車席位分配組合優(yōu)化

劉華森，程文明，張銘奎

(西南交通大學(xué) 機(jī)械工程學(xué)院，四川 成都　610031)

鐵路車票票額的分配是根據(jù)預(yù)測(cè)的客流、歷史的經(jīng)驗(yàn)以及限售條件等因素，為各車站分配所停靠旅客列車的車票票額并對(duì)各種指標(biāo)進(jìn)行計(jì)算。分配給各車站的車票票額會(huì)影響到旅客在各車站購(gòu)票的公平性以及旅客出行的方便性。同時(shí)，車票票額的分配也直接影響到鐵路客運(yùn)收入的高低。由于旅客通過(guò)各個(gè)車站出行的需求是隨機(jī)的和實(shí)時(shí)變化的，從而使得車票票額的分配變得更為復(fù)雜。鐵路部門采取票額共用、席位共用以及票額預(yù)分等銷售策略強(qiáng)化旅客列車的營(yíng)銷和提高客運(yùn)收入水平。為了提高旅客列車的收入和客座利用率(客座利用率=旅客周轉(zhuǎn)量/客座公里總數(shù))，席位拼接以及席位控制等方法逐步成為鐵路運(yùn)營(yíng)管理的熱點(diǎn)研究?jī)?nèi)容。

國(guó)內(nèi)外眾多的學(xué)者對(duì)票額的分配優(yōu)化進(jìn)行了大量的研究，并在收益管理、階梯票價(jià)、隨機(jī)需求、長(zhǎng)途客流保護(hù)等領(lǐng)域取得了重要的研究成果。使鐵路客票收入最大化，是鐵路運(yùn)輸企業(yè)關(guān)心的重要課題。Hetrakul等[1]將旅客潛在的選擇模型和需求函數(shù)納入1個(gè)收入優(yōu)化問(wèn)題，共同考慮定價(jià)和席位分配；研究發(fā)現(xiàn)在相同的容量情況下將短途旅客的需求納入收入管理中會(huì)獲得更多的收入。Peng-Sheng[2]研究階梯票價(jià)對(duì)席位分配的影響，通過(guò)將票價(jià)分為全票價(jià)段和折扣票價(jià)段2個(gè)階段并用約束的非線性整數(shù)規(guī)劃模型，解決席位分配的問(wèn)題。Crevier等[3]提出1種涵蓋定價(jià)和網(wǎng)絡(luò)運(yùn)行規(guī)劃的雙層數(shù)學(xué)模型，并采用基于混合整數(shù)規(guī)劃的思路求解旅客列車的收入。

從保障旅客購(gòu)票的票源以及購(gòu)票機(jī)會(huì)均等性等角度出發(fā)，基于客流預(yù)測(cè)的票額分配方法也得到了廣泛的研究。文獻(xiàn)[4]以時(shí)間序列分析方法建立客流預(yù)測(cè)模型，以旅客列車全程的客座利用率、收入以及整體效益最大化為目標(biāo)，構(gòu)建鐵路車票票額智能預(yù)分系統(tǒng)。包云等[5-7]將單列車的客運(yùn)需求劃分為具有趨勢(shì)規(guī)律的確定需求和具有分布規(guī)律的隨機(jī)需求兩部分，進(jìn)而構(gòu)成單列車的客流量預(yù)測(cè)模型并嵌入隨機(jī)票額分配模型中，實(shí)現(xiàn)隨機(jī)需求與隨機(jī)票額分配有效結(jié)合的單列車票額分配。

在列車席位的分配與安排上，短途客流需求與長(zhǎng)途客流保護(hù)是一個(gè)矛盾的統(tǒng)一體。王洪業(yè)等[8]綜合考慮票額裂解因素、票額保護(hù)因素和客流培養(yǎng)因素，建立站間票額數(shù)量調(diào)配模型，以站間的票額分配數(shù)裂解票額時(shí)所使用的長(zhǎng)途票額最少為目標(biāo)函數(shù)，建立了席位占用優(yōu)化模型。史峰等[9]提出以旅客出行費(fèi)用和票額分配計(jì)劃的人公里數(shù)2項(xiàng)指標(biāo)組成的評(píng)價(jià)方法，設(shè)計(jì)基于票額分配計(jì)劃的換乘網(wǎng)絡(luò)。文獻(xiàn)[10]提出了拼接策略啟動(dòng)時(shí)機(jī)的建議方案，利用余票信息設(shè)計(jì)了拼接票搜索流程，將拼接票的存在性與售票環(huán)節(jié)相分離。Sumalee等[11]提出了1種動(dòng)態(tài)席位分配模型，研究不同類型的旅客在車站等待的概率對(duì)旅客出行方式和出發(fā)時(shí)間的影響。Clausen等[12]將二維背包問(wèn)題用于列車席位的分配，分別討論了當(dāng)列車席位一定時(shí)如何滿足盡量多的旅客乘車需求，以及在乘車需求一定時(shí)如何用盡量少的列車完成運(yùn)輸任務(wù)。Boyar等[13]討論了在允許旅客交換席位的情況下，以旅客移動(dòng)位置最少為目標(biāo)安排旅客的席位。

以上的文獻(xiàn)從宏觀的客票收入、客流預(yù)測(cè)以及席位的具體分配等三方面研究鐵路車票的分配問(wèn)題。但這些研究仍存在列車座位虛糜、客座利用率不高等問(wèn)題。因此，本文以列車的席位分配為切入點(diǎn)，根據(jù)實(shí)際的售票情況提出改進(jìn)的遺傳算法，用于迭代求解和優(yōu)化車票的分配方案，使得旅客列車的客座利用率最大。優(yōu)化的結(jié)果不僅是得到為各個(gè)車站分配的票額，而且也同時(shí)完成了對(duì)應(yīng)各種出行需求的席位分配與組合優(yōu)化，實(shí)現(xiàn)旅客列車席位資源的有效利用。

1　席位的數(shù)學(xué)模型

根據(jù)旅客列車?？慷嗾镜膶?shí)際情況，以列車上的席位與對(duì)應(yīng)的車票為研究對(duì)象，討論分配給各個(gè)車站的票額。

1.1　車票總數(shù)

假設(shè)某列車的席位以及沿途停靠的車站如圖1所示。圖中，S1為列車的始發(fā)站，SN為列車的終點(diǎn)站；N為該列車?？寇囌镜臄?shù)目，且N≥2；該列車中途?？寇囌镜拇涡?yàn)镾2,S3,…,SN-1；A和B分別為席位號(hào)；1和0分別表示席位在行車區(qū)間被占用和未被占用的2種狀態(tài)。

以該列車的某個(gè)具體席位為研究對(duì)象，當(dāng)列車的停站數(shù)目為N時(shí)針對(duì)該席位最多可發(fā)售的車票總數(shù)目TN為

(1)

1.2　席位的狀態(tài)

如圖1(a)所示，因?yàn)橄籄在行車區(qū)間S1→S2的車票已經(jīng)售出，即席位A在該區(qū)間處于被占用狀態(tài)，故記為1；而在行車區(qū)間S2→S3，因?yàn)橄籄的車票沒(méi)有售出，即席位A在行車區(qū)間S2→S3沒(méi)有被占用，則記為0。每個(gè)席位對(duì)于任一行車區(qū)間均只有0或1(未占用或者已經(jīng)占用)2種狀態(tài)。當(dāng)旅客列車?？縉個(gè)車站時(shí)，則共有N-1個(gè)行車區(qū)間，故某個(gè)席位的狀態(tài)在整個(gè)行車區(qū)間中可能出現(xiàn)2N-1次變化。

圖1　列車席位及站點(diǎn)示意圖

1.3　車票組合

在席位的占用中，會(huì)出現(xiàn)席位被若干個(gè)短途區(qū)間車票組合占用的情況。例如，席位B被組合占用的2種情況如圖1(b)所示。情況1，席位B在S1→S2區(qū)間未被占用而在S2→S3和S3→S4區(qū)間分別被2張短途車票占用，可記為011；情況2，席位B在S1→S2區(qū)間未被占用而在S2→S4被1張長(zhǎng)途車票占用，同樣可記為011。同理，110代表席位B也有2種組合占用情況，111代表席位B則可能有4種組合占用的情況，再加上000, 001, 010, 100和101所代表的席位占用情況，故經(jīng)停4個(gè)車站的席位B共有13種組合占用情況。由占用席位的短途車票所經(jīng)過(guò)的短途區(qū)間可以拼接成該席位在多個(gè)相鄰短途區(qū)間被占用的長(zhǎng)途區(qū)間，長(zhǎng)途區(qū)間也可以裂解為若干個(gè)相鄰的短途區(qū)間，因此席位對(duì)應(yīng)的車票組合比席位的占用更復(fù)雜。

本文采用遞推法計(jì)算某席位的車票組合數(shù)目，如圖2所示。設(shè)有N-1個(gè)停車站時(shí)，某席位的車票組合數(shù)目為ZN-1，用圖2中的第1行表示ZN-1中所有可能的車票組合，其中×表示非0即1。當(dāng)增加1個(gè)停車站使得總停車站的數(shù)目為N時(shí)，記該席位上的車票組合數(shù)目為ZN。若在SN-1→SN區(qū)間該席位的占用狀態(tài)為0，則該席位上的車票組合數(shù)目仍為ZN-1；若在SN-1→SN區(qū)間該席位的占用狀態(tài)為1，則由于可能出現(xiàn)短途區(qū)間與長(zhǎng)途區(qū)間的轉(zhuǎn)換，故需要分以下情況討論該席位的車票組合數(shù)目。

圖2　遞推求解示意圖

情況1：如果在第N-1區(qū)間該席位的占用狀態(tài)恰好為0，則該席位的車票組合如第2行所示。情況2：如果在第N-1區(qū)間該席位的占用狀態(tài)恰好為1，則需要進(jìn)一步討論在第N-2區(qū)間該席位的占用狀態(tài)。依次類推直到圖2中的最后一行所表示的車票組合。按照這種遞推方法，圖2恰好被1條取值為0的右斜對(duì)角線分成2個(gè)部分：左上角部分為列車?？康能囌緮?shù)量從2個(gè)車站到前N-1個(gè)車站時(shí)的車票組合數(shù)目Z2，Z3，…,ZN-1；右下角部分為取值1的席位連續(xù)占用情況。以圖2中第3行最后2位為例，2個(gè)連續(xù)取值1表示該席位在SN-2→SN-1和SN-1→SN這2個(gè)區(qū)間連續(xù)被占用。與前面的分析類似，也有可能出現(xiàn)2種情況，即被2個(gè)短途區(qū)間車票占用和或被1個(gè)長(zhǎng)途區(qū)間車票占用，故自動(dòng)形成1個(gè)系數(shù)21；其他情況依此類推，圖2中右側(cè)的系數(shù)則是根據(jù)右下角為1的矩陣推算而來(lái)的。

根據(jù)以上分析可得

ZN=ZN-1+20ZN-2+21ZN-3+…+2N-3+2N-2

(2)

同理可得

ZN-1=ZN-2+20ZN-3+…+2N-4+2N-3

(3)

將式(3)代入式(2)中，可得

ZN=3ZN-1-ZN-2

(4)

式(4)屬于線性常系數(shù)齊次遞推關(guān)系，其特征方程為

x2-3x+1=0

(5)

(6)

ZN隨著列車停站數(shù)目的增加而成指數(shù)倍增長(zhǎng)。由于旅客列車特別是長(zhǎng)途旅客列車?？康能囌緮?shù)量一般較多，當(dāng)停靠的車站數(shù)目增加到一定程度時(shí)，按照傳統(tǒng)的方法已經(jīng)很難為各個(gè)車站分配較為合理的票額，而對(duì)席位的安排則更困難。列車某席位的席位狀態(tài)、可發(fā)售的車票總數(shù)以及車票組合數(shù)目隨著停車站的增加而變化的情況見(jiàn)表1。

表1　列車某席位3個(gè)參數(shù)隨停車站數(shù)目的變化

2　席位預(yù)分策略

2.1　改進(jìn)遺傳算法與車票組合

遺傳算法是解決搜索問(wèn)題的一種通用算法，其共同特征為：首先從初始種群中隨機(jī)選擇1組候選解，依據(jù)某些適應(yīng)性條件測(cè)算這些候選解的適應(yīng)度，根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解。對(duì)保留候選解進(jìn)行交叉操作，生成新的候選解。新的一代將重復(fù)他們父母所進(jìn)行的繁衍過(guò)程，一代又一代演化下去，直到達(dá)到期望的解為止。

在傳統(tǒng)遺傳算法中，遺傳個(gè)體以一定的概率變異，父代的交叉點(diǎn)也具有一定的隨機(jī)性。這是因?yàn)閭鹘y(tǒng)遺傳算法中原始變量的取值范圍一般為連續(xù)區(qū)間，遺傳變異以及隨機(jī)交叉產(chǎn)生的新個(gè)體始終都在這個(gè)范圍內(nèi)，而且同時(shí)還會(huì)加快產(chǎn)生新個(gè)體的速度，從而盡快收斂到目標(biāo)函數(shù)值。但傳統(tǒng)遺傳算法在有整數(shù)約束的組合優(yōu)化算法中卻有一些缺點(diǎn)，比如變異新個(gè)體以及隨機(jī)交叉產(chǎn)生的新個(gè)體很可能是無(wú)意義的個(gè)體，而且會(huì)改變組合優(yōu)化的原始乘車區(qū)間車票需求數(shù)目。因此，結(jié)合鐵路車票票額的實(shí)際情況，本文對(duì)傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，使得在車票組合優(yōu)化算法中始終保持對(duì)原始乘車區(qū)間車票的需求不變。

2.2　車票編碼與組合

設(shè)某旅客列車?？寇囌镜募蟂={Si|i=1,2,…，N}；從停車站Si到其他各停車站Sj(j=2,3,…，N；j>i)的預(yù)測(cè)客流對(duì)應(yīng)的車票的需求為Pij。圖3是以列車上某個(gè)具體席位對(duì)應(yīng)不同車票需求的車票編碼示意圖。為了保證原始乘車區(qū)間車票的需求(原始基因組)在運(yùn)算過(guò)程中不改變，改進(jìn)后的車票編碼分為行車區(qū)間編碼以及判別符號(hào)編碼兩部分。如1.2節(jié)所定義，對(duì)于某席位的狀態(tài)在任何1個(gè)區(qū)間都只有0或1(未占用或者已近占用)2種情況，以此作為車票編碼中的行車區(qū)間編碼。判別符號(hào)編碼是在各個(gè)區(qū)間位置增加符號(hào)判別位，“*”代表此位置可以進(jìn)行交叉運(yùn)算，“#”代表此位置不可以進(jìn)行交叉運(yùn)算。例如圖3中第1行代表所有的行車區(qū)間均被占滿，是一張全程的長(zhǎng)途車票，并且行車區(qū)間內(nèi)不可以進(jìn)行交叉運(yùn)算；圖3中最后一行代表最后一個(gè)行車區(qū)間被占用，是一張SN-1→SN的短途車票，所有的行車區(qū)間可以進(jìn)行交叉運(yùn)算。通過(guò)此種編碼方法，可以將所有客流對(duì)應(yīng)的車票需求進(jìn)行唯一編碼。

圖3　某席位對(duì)應(yīng)不同車票需求的車票編碼示意圖

加入判別符號(hào)位后，可對(duì)某席位車票的組合情況進(jìn)行區(qū)分。對(duì)于由交叉產(chǎn)生的新子代，在對(duì)應(yīng)的交叉點(diǎn)用“&”標(biāo)記，代表2個(gè)父代在此點(diǎn)的連接處可以再次進(jìn)行交叉計(jì)算。以2個(gè)8車站的編碼交叉為例，若F1和F2為父代，且F1表示S2→S5站的短途車票需求，F(xiàn)2表示S5→S7站的短途車票需求，對(duì)應(yīng)的車票編碼分別為

F1=* 0 * 1 # 1 # 1 * 0 * 0 * 0

F2=* 0 * 0 * 0 * 0 * 1 # 1 * 0

本文發(fā)展的TOPSIS算法與現(xiàn)有的R-IGTA算法相比，在優(yōu)化目標(biāo)和對(duì)模塊劃分方案的后處理方面存在明顯的先進(jìn)性。

根據(jù)編碼與交叉的規(guī)則，父代F1和F2可以在S5進(jìn)行交叉運(yùn)算。得到子代f1和f2為

f1=* 0 * 1 # 1 # 1 & 1 # 1 * 0

f2=* 0 * 0 * 0 * 0 & 0 * 0 * 0

子代f1是由父代F1和F2在S5站交叉得到，故f1在S5站的判別符號(hào)記為&。當(dāng)新個(gè)體f1作為父代進(jìn)行下一次交叉運(yùn)算時(shí)，可以一定的概率在S5站解散開(kāi)，從而保證最大限度的交叉組合。子代f2由于不再包含任何有意義的乘車區(qū)間，所以子代f2將被淘汰。在以上定義的車票編碼以及組合交叉運(yùn)算過(guò)程中，原始的乘車區(qū)間車票需求始終被完整的保留和繼承到了下一代個(gè)體中，并且沒(méi)有產(chǎn)生多余的乘車區(qū)間車票需求。這是車票組合優(yōu)化算法的重要前提和保障。

2.3　空間多背包問(wèn)題與車票組合

多背包問(wèn)題(Multiple Knapsack Problem, MKP)[14-15]是指從1個(gè)物品集合中選出1個(gè)物品子集分別裝入M個(gè)背包中, 在不超出每個(gè)包限制容量的條件下, 使選出的全部物品的總價(jià)值最大。傳統(tǒng)的多背包問(wèn)題只考慮物體的體積，并沒(méi)有考慮物體所處的空間位置，而車票的組合問(wèn)題是一個(gè)更為復(fù)雜的多背包問(wèn)題，同樣的乘坐區(qū)間數(shù)由于起始車站的不同而形成不同的車票需求。

對(duì)于屬多背包問(wèn)題且有空間位置的車票組合問(wèn)題，對(duì)應(yīng)其收入和客座利用率的多目標(biāo)函數(shù)為

(7)

s.t

(8)

(9)

(10)

式(8)—式(10)分別為空間位置約束、列車定員約束、票額的上下限約束。

2.4　席位預(yù)分策略

每位旅客對(duì)其乘車區(qū)間的車票需求(原始基因組)具有空間性，這使得車票組合問(wèn)題更為復(fù)雜。同時(shí)，為了保持在運(yùn)算過(guò)程中原始乘車區(qū)間車票的需求不減少也不增加，本文采用改進(jìn)的遺傳組合算法求解這種多維多背包的車票組合優(yōu)化問(wèn)題。圖4是列車席位預(yù)分的車票組合優(yōu)化算法流程。

Step1：車票編碼。以0與1表示席位在某個(gè)行車區(qū)間是否被占用；同時(shí)加入符號(hào)判別位，對(duì)遺傳交叉點(diǎn)的組合情況進(jìn)行區(qū)分。

Step2：父代選擇。父代個(gè)體由隨機(jī)選取產(chǎn)生，即在車票種類范圍內(nèi)智能產(chǎn)生，并且父代所包含的基因組數(shù)目為一定值。

Step3：裂解。根據(jù)列車席位預(yù)分的特點(diǎn)，改進(jìn)裂解的定義為：處于連接狀態(tài)的組合，以一定的概率拆散原始組合以便生成新的個(gè)體，從而尋找最優(yōu)解。2個(gè)交叉的父代根據(jù)適應(yīng)度大小分成父體和母體。適應(yīng)度較小的父體在交叉過(guò)程中首先分解為獨(dú)立的原始乘車區(qū)間車票需求。適應(yīng)度按列車客座利用率和客票收入計(jì)算。

Step4：吸收交叉。基因組具有空間位置，必須按順序進(jìn)行對(duì)應(yīng)點(diǎn)的交叉組合。為了保證每次交叉都朝著結(jié)果更優(yōu)的方向前進(jìn)，采用適應(yīng)度較大的母體和在交叉過(guò)程中吸收接納父體獨(dú)立基因組的方式實(shí)現(xiàn)交叉。不能成功吸收接納的基因組則獨(dú)立成為子代，等待下一次的遺傳交叉。

Step5：選擇與排序。按適應(yīng)度大小篩選最優(yōu)的車票組合，未被選取的客流需求也放入子代內(nèi)等待下一次的組合配對(duì)。

Step6：優(yōu)化準(zhǔn)則判斷。對(duì)于完成1次循環(huán)交叉的子代，按照適應(yīng)度大小進(jìn)行排序，判斷交叉得到的子代是否滿足優(yōu)化準(zhǔn)則條件。不滿足條件時(shí)則再次進(jìn)入下一次吸收交叉循環(huán)，滿足條件達(dá)到優(yōu)化的要求時(shí)則停止計(jì)算。

圖4　組合優(yōu)化算法流程

3　算例分析

以1條包含8個(gè)客運(yùn)站(S1，S2，…，S8)的運(yùn)輸線路為例進(jìn)行算例分析。旅客的車票需求以及相關(guān)的約束見(jiàn)表2所示的矩陣[6]。該矩陣包含各客流對(duì)應(yīng)的車票需求值、最低票額保障值以及相應(yīng)票價(jià)。如該矩陣第1行第2列中的數(shù)值(80,10,40)表示從S1站到S2站的車票需求為80張，最低票額保障為10張，對(duì)應(yīng)的車票價(jià)格為40元·張-1。

表2　車票需求、最低票額保障值和票價(jià)矩陣

采用Matlab編程求解，遺傳種群的規(guī)模隨著遺傳迭代次數(shù)變化的情況如圖5所示。初始種群包含的基因組個(gè)數(shù)(乘車區(qū)間車票需求)約為2 000，優(yōu)化迭代結(jié)束后種群包含的基因組個(gè)數(shù)約為1 400。由于本文對(duì)遺傳算法進(jìn)行了改進(jìn)，因此由2.4節(jié)中的第2步以及第3步可保證在種群規(guī)模減小的過(guò)程中遺傳交叉不會(huì)變異產(chǎn)生新的基因組；同時(shí)通過(guò)吸收交叉的方式也能保證原有的初始基因組不會(huì)減少。由于在迭代運(yùn)算的初期存在大量的短途車票需求，故在迭代的開(kāi)始階段，短途車票會(huì)迅速組合交叉而拼接為長(zhǎng)途席位，使得進(jìn)入下一步迭代的父代數(shù)量急劇減少，而父代所包含的原始車票需求卻不變。在迭代的后期，因?yàn)槎掏拒嚻敝鸩狡唇訛殚L(zhǎng)途席位，交叉產(chǎn)生新子代的概率逐步降低，所以種群的規(guī)模隨著遺傳迭代次數(shù)變化的曲線逐步收斂平緩。

圖5　遺傳種群規(guī)模隨迭代次數(shù)的變化

列車定員分別按600和1 200人情況下列車的客座利用率以及客票總收入如圖6所示。由圖6可知，與圖5類似，在迭代初期客座利用率以及客票總收入均迅速增加；而在迭代的后期，這2項(xiàng)指標(biāo)卻逐步收斂。當(dāng)列車定員為1 200人時(shí)，由于列車的席位數(shù)增加，使得列車的客票收入也相應(yīng)增加，但是客票總收入低于列車定員為600人時(shí)的2倍?？妥寐室驳陀诹熊嚩▎T為600人時(shí)的。依本文例，定員為600人的列車，其最大收入為26.718 5萬(wàn)元，客座利用率為92.57%；定員為1 200人的列車，其最大收入為47.057 0萬(wàn)元，客座利用率為82.04%?？妥寐室约翱推笨偸杖?項(xiàng)指標(biāo)可以為是否增開(kāi)或重聯(lián)旅客列車提供參考依據(jù)。

圖6　客票總收入和客座利用率隨迭代次數(shù)的變化

迭代結(jié)束后種群中基因組包含的乘車區(qū)間數(shù)以及其對(duì)應(yīng)的客票收入情況如圖7所示。由圖7可知，種群中基因組個(gè)數(shù)(乘車區(qū)間數(shù))對(duì)應(yīng)的客票收入也成階梯狀排列。在同樣的乘車區(qū)間數(shù)下客票的收入有略微的波動(dòng)，這是因?yàn)椴煌塑噮^(qū)間組合對(duì)應(yīng)的原始票價(jià)有所差別所致。

圖7迭代后種群中基因組包含的客票總收入以及乘車區(qū)間數(shù)

優(yōu)化后按照列車定員600人和列車定員1 200人時(shí)的車票票額分配方案見(jiàn)表3。表3中，分子表示列車定員為600人時(shí)的票額分配方案；分母表示列車定員為1 200人時(shí)的票額分配方案。

表3　各車站最終車票分配方案　張

4　結(jié)　語(yǔ)

本文根據(jù)鐵路客流的特點(diǎn)，對(duì)遺傳算法進(jìn)行改進(jìn)，在車票編碼中增加判別符號(hào)，同時(shí)對(duì)遺傳的交叉點(diǎn)位置進(jìn)行重新定義，從而保證在遺傳運(yùn)算中原始的乘車區(qū)間車票需求不會(huì)發(fā)生改變。在此基礎(chǔ)上，以列車的客票收入和客座利用率最大為優(yōu)化目標(biāo)，迭代逆向求解屬于多維多背包問(wèn)題的各車站車票分配數(shù)額的優(yōu)化方案。采用本文方法得到不同列車定員情況下的列車客座利用率以及客票總收入，而且當(dāng)列車定員為600人時(shí)，列車的客座利用率可達(dá)92%以上，有效改善了列車座位虛彌問(wèn)題，使得列車的客座利用率以及客票總收入都得到增加，驗(yàn)證了本文方法的有效性。另外，優(yōu)化后的結(jié)果還直接反映出各個(gè)原始乘車區(qū)間車票需求的組合情況，有利于售票時(shí)席位的安排與各站車票票額分配，可為增開(kāi)列車或列車重聯(lián)提供決策依據(jù)。

[1]HETRAKUL P, CIRILLO C. A Latent Class Choice Based Model System for Railway Optimal Pricing and Seat Allocation[J]. Transportation Research Part E: Logistics and Transportation Review，2014, 61: 68-83.

[2]YOU P. An Efficient Computational Approach for Railway Booking Problems[J]. European Journal of Operational Research, 2008, 185(2): 811-824.

[3]CREVIER B, CORDEAU J, SAVARD G. Integrated Operations Planning and Revenue Management for Rail Freight Transportation[J]. Transportation Research Part B: Methodological， 2012, 46(1): 100-119.

[4]單杏花，周亮瑾，呂曉艷，等. 鐵路旅客列車票額智能預(yù)分研究[J]. 中國(guó)鐵道科學(xué)， 2011, 32(6): 125-128.

(SHAN Xinghua，ZHOU Liangjin，Lü Xiaoyan，et al. Research on Intelligent Pre-Assignment of Ticket Allotment for Railway Passenger Train[J]. China Railway Science, 2011, 32(6): 125-128.in Chinese)

[5]BAO Y, LIU J, MA M, et al. Seat Inventory Control Methods for Chinese Passenger Railways[J]. Journal of Central South University, 2014, 21(4): 1672-1682.

[6]包云，劉軍，馬敏書(shū)，等. 高速鐵路嵌套式票額分配方法研究[J]. 鐵道學(xué)報(bào)，2014,36(8): 1-6.

(BAO Yun，LIU Jun，MA Minshu，et al. Nested Seat Inventory Control Approach for High-Speed Train[J]. Journal of the China Railway Society，2014,36(8): 1-6. in Chinese)

[7]包云，劉軍，劉江川，等. 基于隨機(jī)需求的單列車票額分配方法[J]. 中國(guó)鐵道科學(xué)，2015, 36(2): 96-102.

(BAO Yun，LIU Jun，LIU Jiangchuan，et al. Seat Allotment Method for Single Train Based on Stochastic Demand[J]. China Railway Science, 2015, 36(2): 96-102. in Chinese)

[8]王洪業(yè)，呂曉艷，周亮瑾，等. 基于客流預(yù)測(cè)的鐵路旅客列車票額智能分配方法[J]. 中國(guó)鐵道科學(xué)，2013,34(3): 128-132.

(WANG Hongye，Lü Xiaoyan，ZHOU Liangjin，et al. Intelligent Seat Allotment Method for Railway Passenger Train Based on Passenger Flow Forecast[J]. China Railway Science，2013,34(3): 128-132. in Chinese)

[9]史峰，陳彥，周文梁，等. 基于用戶平衡分析的鐵路旅客列車票額分配計(jì)劃制定及評(píng)價(jià)方法[J]. 中國(guó)鐵道科學(xué)，2008, 29(6): 98-103.

(SHI Feng，CHEN Yan，ZHOU Wenliang，et al. Railway Passenger Train Seats Allotment Plan Establishment and Evaluation Method Based on User Equilibrium Analysis[J]. China Railway Science，2008, 29(6): 98-103. in Chinese)

[10]史峰，周俊，陳東方，等. 同一列車不同席位分段拼接售票策略[J]. 鐵道科學(xué)與工程學(xué)報(bào)，2013, 10(5): 71-77.

(SHI Feng，ZHOU Jun，CHEN Dongfang，et al. A Ticketing Strategy of Segmented Stitching Seats in the Same Train[J]. Journal of Railway Science and Engineering，2013, 10(5): 71-77. in Chinese)

[11]SUMALEE A, TAN Z, LAM W H K. Dynamic Stochastic Transit Assignment with Explicit Seat Allocation Model[J]. Transportation Research Part B: Methodological，2009, 43(8/9): 895-912.

[12]CLAUSEN T, HJORTH A N, NIELSEN M, et al. The Off-Line Group Seat Reservation Problem[J]. European Journal of Operational Research，2010, 207(3): 1244-1253.

[13]BOYAR J, KRARUP S, NIELSEN M N. Seat Reservation Allowing Seat Changes[J]. Journal of Algorithms，2004, 52(2): 169-192.

[14]GOKCE E I, WILHELM W E. Valid Inequalities for the Multi-Dimensional Multiple-Choice 0-1 Knapsack Problem[J]. Discrete Optimization，2015, 17(3): 25-54.

[15]馬豐寧，謝龍，鄭重. 求解背包問(wèn)題的基因?qū)傩员Ａ暨z傳算法[J]. 天津大學(xué)學(xué)報(bào)，2010, 43(11): 1020-1024.

(MA Fengning，XIE Long，ZHENG Zhong. Attribute Gene-Reserved Genetic Algorithm for Solving Knapsack Problem[J]. Journal of Tianjin University，2010, 43(11): 1020-1024. in Chinese)