多车型动态需求车辆路径问题建模及优化

Modeling and algorithms for a dynamic multi-vehicle routing problem with Customers' dynamic requests

针对现代物流配送系统中客户需求动态变化、配送中心车型多样化以及车辆行驶路线开放式的特点,建立了多车型开放式动态需求车辆路径问题的两阶段数学规划模型。制定了相应的"预优化路线调度"和"实时动态调度"的两阶段求解策略,提出了混合2-OPT量子进化算法的求解方法,设计了一种将常用的整数编码转换为量子比特的编码方法,每一个染色体都代表一种行车路线方案,对于量子进化算法求得的行车路线方案,引入2-OPT优化方法,对线路内的子路径进行局部调整,进一步提高了算法的收敛速度。最后通过实例测试及与其他算法的比较,验证了该方法的有效性。

Aiming at the dynamic changes of customer requirements,vehicles＇ diversification and open routes in the dynamic vehicle routing problem（DVRP）,a two-phase mathematic programming model was presented for the dynamic vehicle routing problem.Corresponding two-phase solutions of ＂Pre-optimization Route Scheduling＂ and ＂Real-time Dynamic Scheduling＂ were established.And a Hybrid 2-OPT Quantum-Inspired Evolutionary Algorithm（HQEA） for this dynamic problem was proposed.In the HQEA,an encoding method of converting Q-bit representation to integer representation was designed.Every chromosome represented a kind of route.The 2-OPT algorithm was introduced to optimize sub-routes for convergence acceleration.Finally,some examples were tested and were compared with other algorithms.The effectivness of this method was verified by case study and comparing with the other methods.