[發(fā)明專利]一種基于俄羅斯方塊下落的列車分段式座位售票方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011180269.4
• 申請(qǐng)日: 2020-10-29
• 公開（公告）號(hào): CN112308259B
• 公開（公告）日: 2022-09-13
• 發(fā)明（設(shè)計(jì)）人: 丁建勛;朱銳驊;汪森林;黃智圣;張艾霖;所原平;郭寧;龍建成;石琴
• 申請(qǐng)（專利權(quán)）人: 合肥工業(yè)大學(xué)
• 主分類號(hào): G06Q10/02
• 分類號(hào): G06Q10/02;G06Q50/30;G06N20/00
• 代理公司: 安徽省合肥新安專利代理有限責(zé)任公司 34101
• 代理人: 陸麗莉;何梅生

1.一種基于俄羅斯方塊下落的列車分段式座位售票方法，其特征按如下步驟進(jìn)行：

步驟1、假設(shè)一輛列車上的總座位集合記為S＝{S₁,S₂,…,S_m,…,S_M}，S_m表示第m個(gè)座位，且m＝1,2,…,M，令S₀表示無座；令所述列車的車廂數(shù)為C，列車每節(jié)車廂的座位數(shù)為PC，列車每排的座位數(shù)為PR；令Z＝{Z₁,Z₂,…,Z_n,…,Z_N}表示所述列車所經(jīng)過的站點(diǎn)集合，其中，Z₁為列車的起始站，Z_N為列車的終點(diǎn)站，Z_n為列車所經(jīng)過的第n個(gè)站點(diǎn)，且n＝1,2,…,N；以第n-1個(gè)站點(diǎn)Z_n-1與第n個(gè)站點(diǎn)Z_n作為第n-1個(gè)站間區(qū)間F_n-1，則令F＝{F₁,F₂,…,F_n-1,…,F_N-1}表示所有站點(diǎn)的站間區(qū)間集合；

利用式(1)建立所述列車中所有乘客的舒適度目標(biāo)函數(shù)f(x)：

式(1)中，和分別為第k個(gè)乘客在第x個(gè)站間區(qū)間F_x和第y個(gè)站間區(qū)間F_y上的座位信息，％表示取余數(shù)；

步驟2、令所述列車的最大乘客數(shù)為K_max，令當(dāng)前乘客記為第k個(gè)乘客；

步驟3、初始化k＝1，令表示第m個(gè)座位S_m在所有站的站間區(qū)間集合上均有空位；其中，表示第n-1個(gè)座位S_n-1在第n-1個(gè)站間區(qū)間F_n-1上有空位；

步驟4、獲取第k個(gè)乘客從第u個(gè)站點(diǎn)Z_u到第v個(gè)站點(diǎn)Z_v的購(gòu)票信息其中，表示第k個(gè)乘客在第u個(gè)站間區(qū)間F_u上的購(gòu)票信息；

步驟5、令表示第k個(gè)乘客從第u個(gè)站點(diǎn)Z_u到第v個(gè)站點(diǎn)Z_v在第m個(gè)座位上所匹配的站間區(qū)間，其中，定義表示第k個(gè)乘客在第u個(gè)站間區(qū)間的第m個(gè)座位上匹配的站間區(qū)間；

并初始化均為“0”，表示第k個(gè)乘客從第u個(gè)站點(diǎn)Z_u到第v個(gè)站點(diǎn)Z_v的座位信息均為無座；

步驟6、初始化m＝1；

步驟7、將第k個(gè)乘客的購(gòu)票信息P_k與第m個(gè)座位S_m進(jìn)行匹配，得到第k個(gè)乘客在第m個(gè)座位上所匹配的站間區(qū)間

步驟8、判斷的元素個(gè)數(shù)是否與P_k的元素個(gè)數(shù)相等，若相等，則表示第k個(gè)乘客從第u個(gè)站點(diǎn)Z_u到第v個(gè)站點(diǎn)Z_v在第m個(gè)座位上全程區(qū)段有座，并將賦值給將S-S_m賦值給S后，轉(zhuǎn)至步驟14；否則，令m+1賦值給m后，返回步驟7執(zhí)行，直到m＝M為止；

步驟9、定義變量w，并初始化w＝u；

步驟10、初始化m＝1；

步驟11、將第k個(gè)乘客在第w個(gè)站間區(qū)間F_w上的購(gòu)票信息與第m個(gè)座位S_m進(jìn)行匹配，得到第k個(gè)乘客在第w個(gè)站間區(qū)間F_w的第m個(gè)座位上匹配的站間區(qū)間

步驟12、判斷是否成立，若成立，則將m+1賦值給m后，返回步驟11執(zhí)行，直到m＝M為止；否則，將賦值給中的將賦值給S_m，轉(zhuǎn)至步驟13；

步驟13、令u+1賦值給w后，返回步驟10執(zhí)行，直到w＝v-1為止；

步驟14、令k+1賦值給k，并返回步驟4，直到k＝K_max為止；

步驟15、運(yùn)用模擬退火算法來二次分配乘客的座位信息：

定義并初始化模擬退火算法的溫度為T、溫度T的衰減率為A；定義內(nèi)循環(huán)的最大迭代次數(shù)記為L(zhǎng)_max；

步驟16、定義當(dāng)前內(nèi)循環(huán)的迭代次數(shù)為l，并初始化l＝1；

步驟17、計(jì)算舒適度目標(biāo)函數(shù)f(x)的值并作為第l次迭代的目標(biāo)函數(shù)值f(x)_l；

步驟18、用的概率隨機(jī)選擇一個(gè)站間區(qū)間F_n，再用的概率分別隨機(jī)選擇兩個(gè)座位和用于對(duì)分別位于相應(yīng)兩個(gè)座位上的第k₁個(gè)乘客和第k₂個(gè)乘客進(jìn)行換座操作：

將賦值給第k₂個(gè)乘客的并將賦值給第k₁個(gè)乘客的從而分別得到第k₁個(gè)乘客和第k₂個(gè)乘客匹配的站間區(qū)間和

步驟19、求得舒適度目標(biāo)函數(shù)：計(jì)算舒適度目標(biāo)函數(shù)f(x)的值并作為第l+1次迭代的目標(biāo)函數(shù)值f(x)_l+1；

步驟20、計(jì)算第l次迭代的差值Δ_l＝f(x)_l+1-f(x)_l；

步驟21、判斷Δ_l＜0是否成立，若成立，則表示接受換座；否則，生成一個(gè)位于區(qū)間[0,1)的隨機(jī)數(shù)r，并判斷是否成立，若成立，則表示接受換座；否則，取消換座；

步驟22、令l+1賦值給l后，返回步驟17執(zhí)行，直到l＝Lmax為止；

步驟23、令T×A賦值給T后，返回步驟16執(zhí)行，直到T≤1為止；

步驟24、計(jì)算所有乘客二次分配后匹配的座位信息：

步驟24.1、初始化k＝1；

步驟24.2、獲取第k個(gè)乘客所匹配的站間區(qū)間并計(jì)算第k個(gè)乘客所匹配的座位信息：

步驟24.2.1、從中提取匹配的站間區(qū)間

步驟24.2.2、初始化w＝u；

步驟24.2.3、從中提取二次分配前第k個(gè)乘客在第w個(gè)站間區(qū)間F_w上的座位信息并判斷是否成立，若成立，則表示第k個(gè)乘客在第w個(gè)站間區(qū)間F_w上的座位信息為無座；否則，執(zhí)行步驟24.2.4；

步驟24.2.4、令m/PC＝c，其中，/表示上取整，c∈(1,C)，從而得到第k個(gè)乘客在第w個(gè)站間區(qū)間F_w上的車廂序號(hào)c；

令從而得到第k個(gè)乘客在第w個(gè)站間區(qū)間F_w上的座位排號(hào)POR；

令從而得到第k個(gè)乘客的座位列號(hào)POC；進(jìn)而得到第k個(gè)乘客在第w個(gè)站間區(qū)間F_w上的座位為“c車POR排POC列”，將u+1賦值給w，并返回步驟24.2.3執(zhí)行，直到w＝v-1為止；

步驟24.3、令k+1賦值給k，并返回步驟24.2執(zhí)行，直到k＝K_max為止；

步驟25、輸出所有乘客所匹配的二次分配后的座位信息。