基于马尔可夫过程的实时物流VRP建模与求解  

Modeling and Solving Real-Time Logistics VRP Based on Markov Process

作　　者：张玉州 黄子秦 陈文莉 ZHANG Yuzhou;HUANG Ziqin;CHEN Wenli(School of Computer and Information,Anqing Normal University,Anqing 246133,China)

机构地区：[1]安庆师范大学计算机与信息学院,安徽安庆246133

出　　处：《安庆师范大学学报（自然科学版）》2024年第1期90-97,共8页Journal of Anqing Normal University(Natural Science Edition)

基　　金：安徽省自然科学基金面上项目(1808085MF173,1908085MF195)。

摘　　要：在随机车流量环境下,为了有效提高服务质量和减少总运输时间,本文在引入满意度和车流量双指标条件下构建了一种基于马尔可夫过程,以及用于权衡总运输时间和服务惩罚成本的物流服务问题模型。鉴于问题的复杂性,本文设计了一种混合遗传算法对其进行求解,其中基于提高服务质量的局部搜索策略兼顾了车辆总运输时间与客户满意度,使得算法能够在有效空间里进行搜索。为了验证模型和算法的有效性,本文在Solomon数据集的56个测试样例上进行了实验。结果表明,在样例优化服务质量上,所提混合遗传算法在其中28个样例上达到了100%满意评价,较标准遗传算法提高了29%,同时实现了最低总成本目标。To effectively improve the service quality and reduce the total transportation time under the circumstances of stochastic traffic flow,this paper introduces two indicators of satisfaction and traffic flow,and constructs a logistics service problem model that weighs the total transportation time and service penalty cost based on the Markov process.In view of the complexity of the problem,a hybrid genetic algorithm is proposed to solve it in this paper.For the proposed hybrid algorithm,the local search strategy based on Service Quality Improving(SQI)takes into account the total vehicle transportation time and customer satisfaction,so that the algorithm can search in effective space.In order to verify the effectiveness of the model and algorithm,this paper conducted experiments on 56 test examples of the Solomon data set.The results show that the proposed hybrid genetic algorithm achieves 100%satisfaction evaluation on 28 samples in terms of sample optimization service quality.Compared with the standard genetic algorithm,it has increased by 29% while achieving the goal of the lowest total cost.

关 键 词：车辆路径问题 服务质量 马尔可夫模型 混合遗传算法 局部搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]