Pricing strategy of traffic information under double-objective route guidance system
-
摘要: 为了提高交通信息定价精度, 在假定出行者权衡出行时间和出行费用双目标路径诱导的基础上, 建立混合均衡定价模型, 通过实例对模型进行了标定和验证, 对比评价了单目标和双目标路径诱导下的交通信息定价策略, 并给出双目标路径诱导下的交通信息定价结果。研究结果表明, 与双目标路径诱导相比, 单目标路径诱导改变了交通信息定价的可行区域, 当具有信息的出行者、交通信息提供者、交通管理者三方各自的利益为决策主体时, 交通信息的最终价格分别为1.3、2.6和1.8元, 说明了混合均衡定价模型是有效的。Abstract: In order to improve the precision of traffic information pricing, the travel time and travel cost of traveler were considered, a mixed-equilibrium pricing model of double-objective route guidance was established, the model was estimated and validated with numerical example, the comparative evaluation of the pricing strategies of single-objective and double-objective route guidances was carried out, the pricing result of double-objective route guidance was given. Computation result shows that single-objective route guidance changes the feasible region of traffic information pricing compared with double-objective route guidance, the respective interests of information users, information providers and traffic managers are taken as decision-making hosts separately, the traffic information pricings of the model are respectively 1.3, 2.6 and 1.8 RMB, which indicates that the mixed-equilibrium model is effective.
-
车辆路径问题(Vehicle Routing Problem, VRP)是1959年由Dantzig G B等[1]首次提出的, 即已知客户和出发点位置、车辆最大负荷和客户需求, 设计车辆路径, 使运行距离最短。带时间窗约束的车辆路径问题(Vehicle Routing Problem with Time Windows, VRPTW)是在VRP的基础上加上客户要求访问的时间窗约束[2]。40多年来, 许多学者对VRPTW问题进行了深入研究, 尤其是20世纪90年代以来, 遗传算法、神经网络、模拟退火、禁忌搜索等人工智能算法的出现, 为求解VRPTW问题提供了新的工具。其中, Thangiah S R[3]曾用遗传算法求解过VRPTW问题。本文在其基础上提出一种混合遗传算法, 该算法采用一种包含有更多信息的染色体结构, 辅以局部搜索技术, 寻找车辆路经最优解。
1. VRPTW问题的数学模型
VRPTW问题可以描述为出发点O有若干完全相同的车辆将访问n个客户C1、c2、…、cn, 已知车辆载货量为q, 客户ci任务量为di, 1<i<n, 距离矩阵为C=[cij], 0 < i, j < n, cij为ci与cj间的距离, sik为车辆k开始对客户i进行访问的时刻, [ai, bi]为客户ci的访问时间窗约束, 即车辆到达ci的时间最早不能早于ai, 最迟不能晚于bi。要求在上述条件下, 设计车辆路径, 使运行距离最短, 因此, VRPTW问题的数学模型为
约束条件式(2)表示某一车辆任务量之和不大于其容量; 式(3)表示客户i的任务只能由某一辆车完成; 式(4)和式(5)表示两个变量之间的约束关系[4]; 式(6)~(8)保证每辆车始于出发点, 访问客户后, 最后又回到出发点[5]; 式(9)表示时间窗约束。
2. VRPTW问题的混合遗传算法
本文提出了一种混合遗传算法, 即在标准遗传算法中巧妙嵌入一个优化过程, 算法流程如下。
2.1 产生初始种群
本研究采用的是自然数编码方式, 用矢量(s1, s2, …, sn)表示染色体G, 其中元素(基因)sj为[1, n]之间的一个互异自然数。随机产生一组互异染色体Gh(h=1, 2, …, k), 其中k为一代种群中的个体数, 此为第一代种群[6]。
2.2 优化过程
从左向右进行分组, 可将其编码为线路结构, 比如, 染色体: (2, 5, 8, 3, 6, 7, 1, 4)可编码成如下线路结构: ((2, 5, 8)(3, 6, 7)(1, 4))、((2, 5, 8)(3, 6)(7, 1, 4))、((2, 5, 8, 3)(6, 7)(1, 4))等。每一组表示一条路径, 不同分组的染色体表示不同的解。显然, 这些解可行, 但不一定是最优解。
为了找到每个染色体的最佳分组, 把分组信息和每个解联系起来[7], 例如, 染色体可以表示为
新表示中, 括弧内部分是分组信息。[3 3 2]表示前3个客户在第一条线路, 接下来的3个客户在第二条线路。
然后使用λ-交换局部搜索方法在路径之间交换客户, 以改善可行解。该方法是1994年由Osman等[8]提出的一种局部搜索方法。不妨令λ=1, 即路径间至多交换1个客户。λ的取值决定了可定义3种交换操作, 即(0, 1)、(1, 0)、(1, 1)。对一个线路对(RP, RQ)执行操作(1, 1), 含义是1个客户从Rp迁移到RQ, 同时1个客户从RQ迁移到RP。其他操作类似定义, 应沿路径逐一考虑所有客户在每种交换情况下的成本, 目的是寻找导致总成本下降的交换。如果初始分组信息是[3 3 2], 就可检查[2 3 3]、[3 2 3]等, 容易定义搜索顺序和操作。每个新分组将首先进行可行性检查, 只有可行的分组才会被考虑。当然, 搜索策略有2种: 局部最优法和全局最优法。前者当找到第一个导致成本下降的分组时停止搜索, 如果搜索时间结束, 还没有找到新的分组时, 则分组信息不变; 后者则寻找导致成本下降最大解[7]。显然, 后者比前者搜索完备, 但时间长。
2.3 计算适应值
对种群中每个染色体Gh(h-1, 2, …, k), 将上面得到的改善解代入式(1), 求出对应的目标函数值Zh; 若某染色体对应不可行解, 则赋予其目标函数一个很大的整数Zh=M; 令Gh的适应值函数fh=1/Zh, fh是Gh个体生存能力的表现, 越大表明其性能越好, 即其对应的解越接近最优解。
2.4 判断停止进化条件
判断迭代代数是否为要求代数N, 若是, 停止进化, 选性能最好的染色体Gh所对应的路径集合, 作为优化解输出; 反之, 继续执行2.5。
2.5 复制
将每代种群中适应值fh最大的染色体复制后直接进入下一代种群; 剩下的染色体从前代种群染色体中用轮盘旋转法产生。这样既可保证最优个体可以生存至下一代, 又可避免个体间因适应值不同而使被选择进入下一代的机会相差悬殊。
2.6 染色体交叉
对2.5产生的新种群, 按交叉概率pc进行n/2次交叉重组, 交叉规则采用PMX法[9]。设父代的两个染色体为G1=(8, 4, 5, 6, 7, 1, 3, 2), G2=(8, 7, 1, 2, 3, 5, 4, 6), 按PMX法, 交叉重组过程如下
其中交叉交换点k1、k2是随机选取的。对交叉成功得到的子代应用2.2、2.3求得其对应的适应值, 并与其父代进行比较, 择性能优者进入种群。
2.7 染色体变异
在每代种群中以变异概率pm进行染色体变异, 采用随机交换选中染色体内2个基因值的变异策略, 对变异成功的染色体应用2.2、2.3求其适应值, 与父代染色体比较, 择性能优者进入种群。
3. 实验分析
某公司有1家配送中心和8家连锁店, 各连锁店任务量为di(单位: t), 服务时间Ti(单位: h)和配送中心与各连锁店间的距离cij(单位: km), 其中0表示配送中心, 见表 1。服务时间窗口[ai, bi]依次为[6, 9]、[6, 8]、[7, 9]、[8, 12]、[7, 11]、[7, 10]、[7, 10]、[9, 12]。所有配送均由载货量为10 t的车辆完成, 要求合理安排车辆行驶路线, 使总运输里程最短。
表 1 配送任务的特征描述Table 1. Assignment characteristics
使用标准遗传算法对该问题进行求解, 预定进化代数为100, 车辆的行驶路线结果为
总行驶里程为182 km。使用混合遗传算法进行求解, 车辆的行驶路线结果为
总行驶里程为162 km。经验证, 该结果完全满足车辆容量约束和时间窗约束。
4. 结语
本文针对VRPTW问题提出了一种混合遗传算法, 即在标准遗传算法中巧妙地嵌入一个优化过程。在优化过程中, 该混合遗传算法的求解结果随着进化代数的增加而逐渐优化, 当种群失去多样性时再继续迭代下去, 优化结果仍有改善, 并没有出现“早熟收敛”问题; 求出的总行驶里程远远小于使用标准遗传算法求出的总行驶里程, 这说明本文提出混合遗传算法的求解结果大大优于标准遗传算法。
-
图 2 信息提供者利益信息价格变化率与信息价格的关系
Figure 2. Relationship between price and price change rate of information on P
图 3 信息提供者利益信息质量变化率与信息质量的关系
Figure 3. Relationship between quality and quality change rate of information on P
图 4 交通管理者利益信息价格变化率与信息价格的关系
Figure 4. Relationship between price and price change rate of information on Er
图 5 交通管理者利益信息质量变化率与信息质量的关系
Figure 5. Relationship between quality and quality change rate of information on Er
图 6 信息出行者利益信息价格变化率与信息价格的关系
Figure 6. Relationship between price and price change rate of information on Ba
图 7 信息出行者利益信息质量变化率与信息质量的关系
Figure 7. Relationship between quality and quality change rate of information on Ba
图 8 单目标下不同区域内三方利益比较
Figure 8. Comparison of Ba, P, Er in different regions under single-objective guidance
图 9 双目标下不同区域内三方利益比较
Figure 9. Comparison of Ba, P, Er in different regions under double-objective guidance
图 10 单目标和双目标诱导下的可行区域范围比较
Figure 10. Comparison of feasible regions under single-objective and double-objective guidances
图 11 双目标路径诱导下可行区域内的三方利益曲线
Figure 11. Curves of Ba, P and Er in feasible region under double-objective guidance
表 1 单目标下三方利益比较
Table 1. Comparison of Er, Baand P under single-objective guidance
区域编号 Er Ba P 1 > 0 > 0 > 0 2 < 0 > 0 > 0 3 > 0 > 0 < 0 4 > 0 < 0 > 0 5 > 0 < 0 < 0 6 < 0 < 0 > 0 7 < 0 < 0 < 0 
下载: 导出CSV
表 2 双目标下三方利益比较
Table 2. Comparison of Er, Baand P under double-objective guidance
区域编号 Er Ba P 1 > 0 > 0 > 0 2 > 0 > 0 < 0 3 > 0 < 0 < 0 4 < 0 < 0 < 0 5 > 0 < 0 > 0 6 < 0 < 0 > 0
下载: 导出CSV
表 3 定价结果
Table 3. Pricing result
Ba/元 Er/% P/元 (M, θ1) Max(Ba) 2.0 2.0 400 (1.3, 0.58) Max(Er) 1.5 2.0 1000 (1.8, 0.63) Max(P) 0.5 0.3 3000 (2.6, 0.09)
下载: 导出CSV
-
[1] Hong K L, Szeto W Y. A methodology for sustainable traveler information services[J]. Transportation Research: Part B, 2002, 36(2): 113-130. [2] Hong K L, Szeto WY. Modeling advanced traveler information services: static versus dynamic paradigms[J]. Transportation Research: Part B, 2004, 38(6): 495-515. doi: 10.1016/j.trb.2003.06.001 [3] Yang Hai, Meng Qiang. Modeling user adoption of advanced traveler information systems: dymamic evolution and stationary equilibrium[J]. Transportation Research: Part A, 2001, 35(10): 895-912. [4] Yang Hai, Huang Hai-jun. Modeling user adoption of advanced traveler information systems: a control theoretic approach for optimal endogenous growth[J]. Transportation Research: Part C, 2004, 12(3): 193-207. [5] 任刚, 王炜. 基于转向的Logit交通分配算法[J]. 交通运输工程学报, 2005, 5(4): 101-105. http://transport.chd.edu.cn/article/id/200504021Ren Gang, Wang Wei. Turn-based algorithm for Logit traffic assignmen[J]. Journal of Traffic and Transportation Engineering, 2005, 5(4): 101-105. (in Chinese) http://transport.chd.edu.cn/article/id/200504021 [6] 四兵锋, 孙壮志, 赵小梅. 基于随机用户平衡的混合交通网络流量分离模型[J]. 中国公路学报, 2006, 19(1): 93-98. doi: 10.3321/j.issn:1001-7372.2006.01.020Si Bing-feng, Sun Zhuang-zhi, Zhao Xiao-mei. Mixedtraffic network flow-split model based on stochastic user equilibrium[J]. China Journal of Highway and Transport, 2006, 19(1): 93-98. (in Chinese) doi: 10.3321/j.issn:1001-7372.2006.01.020 [7] 李志纯, 黄海军. 多目标路径诱导下平衡市场渗透率的确定[J]. 系统工程理论与实践, 2004, 9(9): 125-130. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200409021.htmLi Zhi-chun, Huang Hai-jun. Determination of equilibrium market penetration under multi-criteria route guidance systems[J]. Systems Engineering-theory & Practice, 2004, 9(9): 125-130. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200409021.htm [8] Yang Hai. Multiple equilibrium behavior and advanced traveler information systems with endogenous market penetration[J]. Transportation Research: Part B, 1998, 32(4): 205-218. [9] 张培爱. 互补问题的有效算法研究[D]. 大连: 大连理工大学, 2002. [10] Hong KL, Szeto WY. Acell-based variational inequality formulation of the dynamic user optimal assignment problem[J]. Transportation Research: Part B, 2002, 36(5): 421-443. -
下载:
点击查看大图
计量
- 文章访问数: 302
- HTML全文浏览量: 82
- PDF下载量: 398
- 被引次数: 0
