停站约束下多列车运力分配与定价联合决策模型

江文辉，徐 菱*,1b，李延来,1b，李思雯，丁小东

(1.西南交通大学a.交通运输与物流学院，b.综合交通运输智能化国家地方联合工程实验室，成都610031；2.中国铁道科学研究院运输与经济研究所，北京100081)

0 引言

铁路是我国货物运输的主要承担者，但近年来随着航空、公路等多种运输方式的快速发展，铁路货运总量持续下降.为扭转铁路货运量逐年下滑的困境，2013年铁路实行货运改革，货改的一项主要内容是货运市场的定价权将逐步放开，由企业自主定价，自此铁路货运市场迸发出新的活力.

对于特定开行的货运班列，通常运力较为固定且不可储存，因此在运力固定、需求不确定及预售期有限等硬性约束条件下，如何对货运班列的运力进行有效管理以获得最大收益，是铁路货运企业面临的重要决策.基于此，本文利用收益管理的思想，针对货运企业面临的运力分配和定价问题展开研究，以期为铁路货运企业有效控制运力提供科学的决策依据.

关于运输问题中的运力(存量)控制和定价问题，国内外许多学者已做了一些有益的研究：Lee等[1]研究了海运集装箱运输的箱位分配问题，并给出了最优分配的阀值策略；Lu等[2]构建了考虑联盟协议情况的舱位优化互换分配和定价联合决策模型；卜祥智等[3]建立了考虑和不考虑货主价格参考效应2种情形下两级海运链的运力分配和定价联合决策模型；Levin等[4]研究了多条平行货运航班在合同市场和现货市场的运力控制问题，上述研究问题的背景均缺乏铁路运输多列车、多站段的网络特性.杨华龙等[5]研究了集装箱班轮运输中2个市场的舱位分配和定价问题，随后刘迪等[6]将模型拓展到多节点海铁联运情形，虽然也建立了随机非线性模型，但最后都转化为确定性模型进行求解，缺少对需求随机性的探讨.You等[7]针对多站段2个票价等级的铁路票额分配问题建立了1个概率非线性整数规划模型，并设计粒子群算法求解；赵翔[8]、钱丙益[9]等在此基础上分别研究了多列车多停站方案情形和考虑顾客buy-up行为情形的票额分配问题，研究内容针对客运铁路，并不完全适用铁路货运问题；Hellermann[10]等从契约理论的角度研究运输双市场的运力分配或定价问题.

此外，注意到列车的停靠方案直接影响着列车的运力分配，但目前考虑列车停站约束的运力控制问题的研究成果甚少，文献[8]虽然考虑了列车的停站问题，但是将列车的停站方案设定为已知条件且研究背景是客运铁路.关于列车停站问题的研究成果可参考李得伟[11]等学者.

针对以上不足，本文将考虑列车停站约束和2个市场需求的随机性，以期望收益最大化为目标建立运力分配和定价联合决策的混合整数概率非线性规划模型，并设计粒子群算法对模型求解.

1 模型建立

1.1 问题描述和符号说明

假设某一个铁路货运企业经营1条包含N个站点的铁路货运线，某一时段可开行K列列车，每列货运班列的最大运力为Ck，不允许超售.定义相邻2个站点构成的路程称为区段，1个或多个区段构成了铁路运行的路径称OD.货运企业面临的货运市场可分为由大客户组成的合同市场和由零散客户组成的自由市场.合同市场上各OD对(i,j)的运力需求是较为稳定的大客户，需求量表现为某种概率分布，其概率密度函数和分布函数可分别设为fij(∙)、Fij(∙)，相应OD上运力的单位运价为自由市场面临的是货运量需求波动较大的零散客户，可用关于运价的线性函数来描述，并用随机需求因子来刻画自由市场需求的波动性，即dij=αij-βij riBj+εij，其中，系数αij,βij的取值需要根据历史数据采用统计方法估计出来为自由市场关于OD对(i,j)的单位运价，εij为随机变量，不妨设其服从[-eij,eij]上的均匀分布.相关符号说明如下：

S——铁路货运企业所经营的1条铁路运输线所包含的铁路货运站点集合，S={i|i=1,2,…,N}，易知该铁路运输线共有N-1个运行区段，可用m来索引区段序列，即m=1,2,…,N-1；

G——铁路货运企业在该条铁路运输线上可开行的列车集

Ckm——列车k在区段m上的最大货运能力，通常取Ckm=Ck，k=1,2,…,K，m=1,2,…,N-1；

(i,j)——列车运行路径(OD对)，∀i,j满足1≤i＜j≤N；

yki——列车k在车站i的停站决策，若yki=1，则列车k在车站i停靠，yki=0时反之，∀i∈S，∀k∈G；

决策变量：

yki——列车的停站约束决策，为0-1变量，∀i∈S,∀k∈G，变量个数为KN，记 为y=(y11,y12,…,y1N,…,yk1,yk2,…,ykN,…).

1.2 目标函数

目标函数就是铁路货运企业的收益最大化.铁路货运企业的收益分为合同市场和自由市场2个部分，首先分析合同市场的收益情况.

综上可知，是铁路货运企业的总收益为

1.3 约束条件

(1)区段容量约束.

对于任意区段m(m=1,2,…,N-1)，列车k(∀k∈G)在区段m上的合同市场和自由市场的运力分配量之和不能大于列车k在区段m上所能提供的最大运力，即

(2)列车停站约束.

影响列车停站的因素有很多，如：车站接发列车能力、站点服务频率、列车最大停站数目、客流量约束和列车停站模式适应性等.为简化问题，本文主要考虑站点服务频率、列车停站数目及站间服务可达性3个因素.

(a)站点服务频率约束，是指对于某个车站i(i=1,2,…,N)，要求在给定时间段其服务频率不得低于fi(次/单位时间)，即

(b)列车停站数目约束，列车停站数量会影响列车的运行速度，增加货物的在途时间，影响铁路货运的时效性，而列车停站数目较少又难以承接足够的货运量，导致列车的运力不能够得到充分利用.因此需要在效率和效益之间取得平衡，可为每列列车设置1个停站数目的下限和上限，即

(c)站间服务可达性约束，考虑到N个货运车站中，车站的等级、货运站间货运周转量都不相同，因此会要求某两个车站之间有直达班列，基于此可用式(9)来描述车站i与车站j(i＜j)间的直达关系.

(3)自由市场定价约束.

铁路货运企业在自由销售市场将面临大量的零散客户，此时铁路货运企业处于主导地位即货运企业具有一定的定价权.一般来说，此时自由市场在每个OD上的运价应不小于相应的合同运价，且不大于相应的价格上限，即

由上述目标函数和约束条件，整理可得停站约束下多列车运力分配与定价联合决策模型(M1)为

2 模型求解

模型(M1)为混合整数概率非线性规划问题，求解该类问题常采用遗传算法、模拟退火算法等启发式算法，粒子群算法具有群体智能、内在并行性、迭代格式简单、占用内存空间小、可快速收敛到最优解所在的区域等优点，在求解大规模问题尤其是NP难问题等方面得到广泛应用.因此，本文基于粒子群算法的思想求解该问题.具体算法步骤如下：

Step 1种群规模、迭代次数及种群中各粒子位置和速度的初始化.设种群规模为L，最大迭代次数为tmax，粒子初始位置的获取通过求解模型(M2).

模型(M2)是将模型(M1)中自由市场和合同市场的随机需求用其期望值代替的确定性模型，可通过常用的求解软件(如LINGO)很容易求得模型(M2)的解由此可定义第l(1≤l≤L)个粒子的初始解为，若问题的搜索空间为D维，则每个微粒向量中包含D个分量，即

式中：cl——各分量服从(-c,c)上的均匀分布，c为整数，其大小可以根据实际情况而定.

Step 2计算每个微粒的目标函数值(即适应度值).设为第l个粒子在第t(1≤t≤tmax)次迭代的位置，记为第l个粒子在第t次迭代时的函数值，在计算适应度值时，由于变量中存在整数约束条件，因此需要对部分分量进行四舍五入取整处理.

Step 3更新粒子的位置和速度.设为第l个粒子在第t次迭代时的速度，粒子的速度更新公式为式(30)，位置更新公式为式(31).

式中：w——惯性权重，为避免算法早熟和后期在全局最优解附近产生振荡现象，可以采用线性变化的权重，让惯性权重从最大值wmax线性减少到最小值wmin，w的迭代次数t的公式为w=

λ1,λ2——正的学习因子；

γ1,γ2——0～1均匀分布的随机数；

Step 4计算位置更新后的每个粒子的适应度，将每个微粒的适应度与以前经历过的最优位置所对应的适应度值作比较，如果更新后微粒的适应度值较优，则将其当前的位置作为该微粒的

Step 5将每一个粒子的适应度值与整个粒子群的最好位置比较，如果较好，则更新粒子群的全局最优解

Step 6检查是否满足终止条件(通常判断是否达到最大迭代次数tmax)，如果达到终止条件则算法终止，输出最优解，否则返回Step4.

3 算例分析

考虑某一个货运企业经营1条包含6个车站的铁路货运线，某一时段可开行2列货运班列，最大运力分别为2 500和2 000.此外，通过历史数据可以统计出合同市场的需求状况，可知合同市场各个OD对的需求服从正态分布，参数取值如表1所示.自由市场各个OD的需求参数如表2所示，同时为简化问题可设自由市场各个OD随机需求因子εij均服从区间[-30,30]上的均匀分布，表3给出了各个OD在合同市场的单位运价和自由市场定价的价格上限.

假定列车的停站约束为：①2列货运班列在起点车站(车站1)和终点车站(车站6)必须停靠；②列车1和列车2的停站数目的下限和上限分别为[3,5]和[3,4]；③要求车站4到车站6至少有1列车直达；④所有车站的服务频率至少为1次.

粒子群算法的相关参数设定：种群规模为L=40，最大迭代次数tmax=300，惯性权重wmax=0.9，wmin=0.4，学习因子λ1=λ2=0.5.然后通过Matlab工具编程求解可得到：各货运班列在合同市场和自由市场的运力分配量如表4所示；自由市场各OD的单位运价如表5所示；以及列车的停站方案，如图1(a)所示.

表1 合同市场各个OD对参数(μij,σij)Table 1 OD parameters of alloment markrt(μij,σij)

表2 自由市场市场的OD对参数(αij,βij)Table 2 OD parameters of spot market(αij,βij)

表3 价格参数(,)Table 3 Price parameters(,) (元/单位运力)

表3 价格参数(,)Table 3 Price parameters(,) (元/单位运力)

175,90141,170214,256293,350325,390 2—67,80139,167218,260250,300 3—72,87152,183184,220 4—79,95111,135 5————40,50

表4 2个市场运力分配情况Table 4 Capacity allocation results

表4 2个市场运力分配情况Table 4 Capacity allocation results

1239,324,0,00,0,245,4340,0,586,595198,381,0,0542,818,136,7 2—0,0,0,00,0,0,00,3,0,0129,428,0,0 3—0,0,2,290,0,0,00,0,215,429 4—0,0,0,00,0,475,738 5— — — —174,294,0,0

表5 自由市场各OD的定价方案Table 5 Each OD pricing results for spot market(元/单位运力)

图1 不同情况下列车停站方案Fig.1 Train stop schedule plan under different circumstances

以相同的列车停站约束条件和市场需求数据，采用2个市场统一定价策略，即统一采用合同运价，可得到2个市场的运力分配情况和列车停站方案分别如表6和图1(b)所示.此外，通过计算可知2个市场差异化定价可获得期望收益为1 463 583元，2个市场统一定价可获得期望收益为1 450 275元，即采用2个市场差异化定价可使期望收益增加13 308元.

进一步分析市场需求波动对铁路货运企业收益的影响.图2给出了自由市场在不同随机需求因子εij取值情况下，采用2个市场差异化定价相对于2个市场统一定价期望收益提高的比例，可知，自由市场需求波动越大，采用2个市场差异化定价策略越优.

图2 自由市场随机需求因子εij对总期望收益提高的影响Fig.2 The effect of spot markrt stochastic demand factorεij on the total expect revenue

表6 统一定价策略下2个市场运力分配情况Table 6 Capacity allocation results under the unified pricing strategy

表6 统一定价策略下2个市场运力分配情况Table 6 Capacity allocation results under the unified pricing strategy

1236,321,0,0245,428,0,0322,894,0,00,0,160,3460,55,679,811 2—15,17,0,00,0,0,00,0,0,0258,266,0,0 3—0,0,0,00,0,0,0210,494,0,0 4—0,0,0,0476,739,0,0 5— — — —0,0,180,288

4 结论

本文针对铁路货运企业面临的合同、自由双市场运力控制和定价问题，建立了一个考虑多列车停站约束、2个市场运力分配和定价的混合整数概率非线性规划模型，并设计粒子群算法求解，通过算例验证了模型和算法的有效性.此外，本文以2个市场统一定价策略所得的运力分配结果为对比方案，结果表明，实施2个市场差异化定价能够显著增加货运企业的收益，且自由市场需求波动性越大收益增加越明显.但是本文采用的运力分配和定价策略仍属于静态策略，在整个运力销售周期对运力和运价进行动态控制将具有重大意义，列车的停靠方案除了满足特定的硬性约束条件外，还应该考虑列车满载率、客户满意度等问题都有待进一步研究.

[1]LEE L H,CHEW E P,SIM M S.A revenue management model for sea cargo[J].International Journal of Operational Research,2009,6(2).

[2]LU H A,CHEN S L,LAI P.Slot exchange and purchase planning of short sea services for liner carriers[J].Journal of Marine Science&Technology,2010,18(5):709-718.

[3]卜祥智,许垒,赵泉午.考虑货主价格参照效应的海运运力合同定价策略[J].管理科学学报,2012,15(2):28-36.[BU X Z,XU L,ZHAO Q W.Study on Marine shipping contract allocation and pricing under shipper’s pricing reference effects[J].Journal of Management Sciences in China,2012,15(2):28-36].

[4]LEVIN Y,NEDIAK M,TOPALOGLU H.Cargo capacity management with allotments and spot market demand[J].Operations Research,2012,60(2):351-365.

[5]杨华龙,刘迪,王霞,等.集装箱班轮运输两阶段舱位分配与动态定价模型[J].系统工程理论与实践,2012,32(12):2684-2691.[YANG H L,LIU D,WANG X,et al.Slot allocation and dynamic pricing models by two stages for container liner shipping[J].Systems Engineering-Theory&Practice,2012,32(12):2684-2691.]

[6]刘迪,杨华龙,张燕.多节点集装箱海铁联运动态定价决策[J].系统工程理论与实践,2014,34(1):104-114.[LIU D,YANG H L,ZHANG Y.Dynamic pricing decision-making of multi-node container sea-rail intermodal transport[J].Systems Engineering-Theory&Practice,2014,34(1):104-114.]

[7]YOU P S.An efficient computational approach for railway booking problems[J].European Journal of Operational Research,2008,185(2):811-824.

[8]赵翔,赵鹏,李博.多列车多停站方案条件下高速铁路票额分配研究[J].铁道学报,2016,38(11):9-15.[ZHAO X,ZHAO P,LI B.Study on high-speed railway ticket allocation under conditions of multiple trains and multiple train stop plans[J].Journal of the China Railway Society,2016,38(11):9-15.]

[9]钱丙益,帅斌,陈崇双,等.基于旅客buy-up行为的铁路客运专线收益管理模型[J].铁道学报,2013,35(8):10-15.[QIAN B Y,SHUAI B,CHEN C S,et al.Revenue management model for dedicated passenger line based on passengers’buy-up behavior[J].Journal of the China Railway Society,2013,35(8):10-15.]

[10]HELLERMANN R,HUCHZERMEIER A,SPINLER S.Options contracts with overbooking in the air cargo industry[J].Decision Sciences,2013,44(2):297-327.

[11]李得伟,韩宝明,李晓娟,等.基于节点服务的高速铁路列车停站方案优化模型[J].铁道学报,2013,35(6):1-5.[LI D W,HAN B M,LI X J,et al.High-speed railway stopping schedule optimization model based on node service[J].Journal of the China Railway Society,2013,35(6):1-5.]