带实际约束的大规模车辆路径问题建模及求解

针对现有算法不能有效求解卷烟配送过程中, 问题规模大并具有诸多实际约束条件限制这类实际问题, 首 先分析实际约束, 建立问题模型; 然后从模型出发设计多阶段算法, 通过地理信息的分级管理实现区域划分, 在降低 问题规模的同时消除交通障碍; 采用改进的k 均值聚类法分派线路, 将问题转化为求解小规模旅行商问题; 最后以济 南市区的卷烟配送为例, 通过与典型优化算法的比较表明了所提出多阶段算法在实际应用中的优越性.

Modeling and solving large-scale vehicle routing problem with practical constraints

Because of the large scale and practical constraints, the real-life application related to cigarette distribution can’t be efficiently solved by existing methods. Firstly, a model based on the analysis of practical constraints is built. Then a multi-stage algorithm based on the model is proposed. Dividing based on geographic information grading can reduce the problem scale and eliminate geographic obstacles. The modified ??-means clustering method is used to dispatch routes, and the original problem can be translated into small scale traveling salesman problem. Finally, taking the cigarette distribution in Ji’nan city as an example, compared with several excellent methods, the advantage of multi-stage algorithm used in real-life is verified.