不确定同时取送货车辆路径问题及粒子群算法研究

研究了不确定同时取送货车辆路径问题(VRPSPD),考虑运行环境的不确定性,顾客时间窗口要求和对顾客同时进行取货和送货服务的情况,以运作成本最低和顾客满意度最高为决策目标,构建不确定VRPSPD数学模型。模型中,引入模糊随机理论来描述决策环境中的双重不确定性,假定顾客需求量(送货量)和取货量是模糊随机变量。随后,提出基于模糊随机算子的改进粒子群算法对模型进行求解。为了适应模型特点和提高算法效率,设计合理的编码和解码过程,制定多个适应度函数方案处理多目标问题,并应用更加科学的更新策略。最后在应用案例中,通过参数测试获取合理的算法参数取值,采用计算结果分析和求解算法测评验证模型和算法的有效性。

An Improved Particle Swarm Optimization for Simultaneous Pickup and Delivery Vehicle Routing Problems with Time

This article studies the vehicle routing problem with simultaneous pickup and delivery(VRPSPD)under a fuzzy random environment, considering the uncertainties in the operational environment, the customer’s time requirements, and the situation of simultaneous pickup and delivery for customers. A mathematical model is formulated for the uncertain VRPSPD, where the objectives are to seek the most economic route for each vehicle with the minimum operational cost and to maximize the customer satisfaction in the same time. In this model, the fuzzy random theory is used to describe the double uncertainties in the decision environment, namely assuming the delivery amount(customer’s demand)and pickup amount are fuzzy random variables. And then, an improved hybrid particle swarm optimization with fuzzy random simulation is proposed to solve the model. Chance constrained operator is used in constraints to deal with the random fuzzy variables in this model. More specifically, to adapt to the mathematical model and improve the algorithm performance, this approach makes improvements and modifications in encoding and decoding, multi-objective handling, and particle updating. The encoding and decoding are suitable for the VRPSPD, multiple fitness functions are used to deal with the multi-objectives, and the improved update function can help overcome the shortcomings of the basic particle swarm optimization(PSO). Finally, in the case study, parameter tests and results analysis are presented to highlight the performance of the optimization method, and algorithm comparison demonstrates its efficiency.