大连海事大学学位论文

在VRP问题中，假设有一个供求关系系统，车辆从仓库取货，配送到若干个顾客处。车辆受到载重量的约束，需要组织适当的行车路线，在顾客的需求得到满足的基础上，使代价函数最小。代价函数根据问题不同而不同，常见的有车辆总运行时间最小，车辆总运行路径最短等。 这个问题基于以下假设： 定义 为需要服务的两个顾客编号， 为配送中心的车辆编号， 为顾客和仓库的集合。 参数： : 从顾客 到顾客 的行驶距离 ：顾客 的需求量 ：车辆的最大载重量 决策变量： ：当车辆 被分配从顾客 运行到顾客 时，取1；否则取0 在给定了参数和定义了决策变量之后，VRP问题可以用数学模型表示为：给定车辆负载为400，各个节点的坐标和需求如下(节点0为配送中心)： 对于个体采用自然数编码，0代表配送中心，1--n代表顾客；不同车辆的配送路线之间用0分隔（即每辆车都从仓库出发）；对于有n个顾客，k辆车的VRP问题来说，染色体长度为n+k+1。 例如配送中心有3辆车为8个客户服务，一条可能的染色体如下： 0, 7, 0, 1, 2, 3, 5, 0, 8, 4, 6, 0 这条染色体表示的三辆车的行驶路线为: 第一辆车：0-7-0 第二辆车：0-1-2-3-5-0 第三辆车：0-8-4-6-0 利用分割符0，还原各条子路径 参考了大连海事大学硕士学位论文《基于电动汽车的带时间窗的路径优化问题研究》中的交叉操作，生成新的个体，具体描述如下图： 用2-opt算法对各条子路径进行局部优化 输出计算结果： 迭代过程如下图所示： 总共使用了4辆车，各自的行驶路径如下：