快递公司的配送数学建模.doc

快递公司的配送问题摘要 配送是物流系统中非常重要的一个环节，在物流的各项成本中，配送成本占了相当高的比例，减少配送里程以降低物流配送成本成为物流管理过程中首要考虑的问题之一本文在已知货运车容量、各客户所需货物重量、快递公司和客户以及客户和客户之间的距离的条件下，建立了以单车场路径问题模型（即VRP模型）为基础、以车辆总行程最短为目标函数、以货物运输量小于汽车载重量以及在客户要求的时间范围内运送货物等为约束条件的单目标线性规划模型　 对于问题一，本文建立了两个模型：模型I：硬时间窗车辆路径规划模型　 首先根据题目所给条件，对运货所需的车辆数进行预估，然后结合货物运输量小于汽车载重量、一个客户点的货物仅由一辆车配送等约束条件，同时考虑线路的连通性和汽车到达客户点的时间范围，采用0-1规划法建立使总运行里程最小的车辆路径规划模型　 模型II：软时间窗车辆路径规划模型在模型I硬时间窗车辆路径规划模型的基础上，将模型I中的关于时间范围的约束条件，通过设定惩罚函数的系数，变成目标函数的一部分本文在考虑路程最短的目标的同时，也要求尽可能在时间范围内到达因此，建立了以成本（包括惩罚成本以及行驶过程中带来的成本）最小为目标的函数，以运输量小于汽车载重量以及线路的连通性等为约束条件，建立软时间车辆路径规划模型。

最后运用遗传算法求解模型  对于问题二，根据题目所提供的数据，利用硬时间窗车辆路径规划模型首先，根据货运车的载重量和客户点的需求总量，估计出运货所需车辆数为3，然后，借助Lingo求解该模型得到最优路径的总里程数为910千米，快递公司每天的配送方案应为:每天出动3辆车3辆车的行驶路径分别为：0->3->1->2->0，0->6->4->0，0->8->5->7->0关键词： VRPTW 遗传算法 0-1规划法 Lingo / / 目录一、问题重述 2二、模型假设和符号说明 2三、问题分析 3四、模型的建立和求解 44.1问题一的解答 44.1.1模型的准备 44.1.2模型的建立 44.1.3模型的求解 74.2问题二的解答 84.2.1对货运车辆数的估计 84.2.2路线的规划 8五、 模型的评价和改进 105.1模型的优缺点分析 105.2 模型的改进 11六、参考文献 11七、附录 12一、问题重述某快递公司在某个地区拥有一支货运车队，每台货运车辆的载重量（吨）相同、平均速度（千米/小时）相同，该快递公司用这样的车为若干个客户配送物品，快递公司和客户以及客户和客户之间的公路里程（千米）为已知。

每天，各客户所需物品的重量（吨）均已知，并且每个客户所需物品的重量都小于一台货运车辆的载重量，所有送货车辆都从快递公司出发，最后回到快递公司快递公司每天的配送方案应当包括：当天出动多少台车？行驶路径如何？由此形成的当天总运行里程是多少？一个合格的配送方案要求送货车辆必须在一定的时间范围内到达客户处，早到达将产生等待损失，迟到达将予以一定的惩罚；而一个好的配送方案还应该给出使配送费用最小或总运行里程最短的车辆调度方案该快递公司希望你们：1. 建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法2. 具体求解以下算例，并给出你们实际使用的软件名称、命令和编写的全部计算机源程序〔算例〕载重量为 8 吨、平均速度为 60千米/小时 的送货车辆从快递公司（0）出发，为编号是 1，2，…，8 的8个客户配送物资某日，第个客户所需物品的重量为吨（），在第个客户处卸货时间为小时，第个客户要求送货车辆到达的时间范围 由表1给出快递公司和各客户以及各客户间的公路里程（单位：千米）由表2给出问当日如何安排送货车辆（包括出动车辆的台数以及每一台车辆的具体行驶路径）才能使总运行里程最短 二、模型假设和符号说明2.1模型假设1、所有的货运车辆都没有超载。

2、 快递公司能提供充足的货运车辆3、 一个客户点只有一辆货运车进入和离开4、 每条配送路径都在货运车辆的配送范围内5、 同一个客户所需要的物品只由一辆货运车配送6、 不考虑货物的类型和货运车的车型，货物可混装7、 不考虑货运车速度及运输时间因天气、交通等因素的影响8、 快递公司和客户以及客户和客户之间的距离、每天各客户所需物品的重量均视为不变2.2符号说明m 派出的货运车辆总数N 客户的数量Q 每台送货车的载重量 第i个客户和第j个客户之间的距离 第i个客户所需货品的重量v 每台送货车的平均速度 送货车从客户点i到客户点j所需要的时间 送货车到i的时间 送货车在客户点i卸货的时间 第i个客户要求送货车到达的时间范围的下限 第i个客户要求送货车到达的时间范围的上限三、问题分析 这是一个单配送中心、多客户点、非满载、带有时间窗的车辆配送路线问题（简称VRPTW）问题的解决在于对一系列客户点，组织适当的行车路线，使货运车有序地通过它们，在满足一定的约束条件（各客户点货物需求量、交货时间、车辆载重限制等）下，达到总行程最短的目的 问题一：题目要求建立送货车辆每天总运行里程最短的一般数学模型。

因为问题要求制定的配送方案和车辆数目和时间（包括：卸货时间和送货途中所需时间）有关，所以,首先对运货所需的车辆数进行预估通过讨论时间窗口是硬窗口还是软窗口，本题分别建立了两个数学模型对于硬窗口的VRPTW问题，送货车必须在给定的时间范围内到达客户点，所以加入对每辆运货车到达客户点的时间限制，综合求出总里程数最短的路线而对于软窗口的VRPTW问题，没有严格的时间限制但是，货车早到或晚到产生的损失和惩罚会对配送公司的成本产生影响，所以，配送方案应该保证车辆行驶里程最短，且尽可能的在客户点要求的时间范围内到达 问题二：基于问题一的模型，将具体数据代入模型，即可求出最短的路程方案首先根据总配送量和运货车载重限制约束，求出送货运车派遣辆数然后根据配送中心目标和客户点之间距离等，确定目标函数即最短行程模型根据目标函数和时间窗约束，采用数学软件Lingo9.0编写程序，最终得出各货运车的行程线路四、模型的建立和求解4.1问题一的解答4.1.1模型的准备为了安排路线，我们首先要对送货车的数量进行估计约束条件越多，则安排线路越难，一辆车完成的任务越少，安排的车辆越多我们可以按下述公式[1]估计所需货车的数量。

其中，表示取整，a为参数，且0

式（12）：表示配送公司成本最小的目标式（13）：表示每个客户点有且仅有一辆车进入式（14）：表示每个客户点有且仅有一辆车离开式（15）：表示任务i只能由一辆车完成式（16）：表示每辆车的实际运载量不能超过它的容量式（17）（18）（19）：表示车均从配送中心出发，经过若干不重复的客户，最后重新回到配送中心式（20）：表示送货车辆到达j的时间=车到达i的时间+在i卸货的时间+i，j间行驶所需的时间式（21）：i，j客户点间的运输时间由 时间=路程/速度 公式求得4.1.3模型的求解求解车辆路径规划模型的方法有：禁忌法、模拟退火法、遗传算法和门槛接受法等基于以上建立的模型，综合考虑各种算法后，我们选择使用遗传算法[2]对该模型进行求解遗传算法的步骤如下：①编码 采用自然数编码, 即序数编码单车场非满载VRP 的一条可行线路可编成长度为N+m的染色体, 其中 表示第k辆车完成的第n项任务0 表示车场0, m 为完成任务所需要的车辆数 ②产生初始群体 初始群体随机产生, 即产生N项货物运输任务点的全排列, 如, 若且, 将s 至N的基因逐一向后移动一位, 将0 插入到第s 位。

接着, 若且, 如前操作, 使t 位空出, 插入0; 如此, 直到将m 个0 全部插入染色体为止这样构成了一条初始染色体, 如此反复, 直到满足群体数 ③适应度函数 适应度函数取, 其中 为染色体的适应度, b 为常数, 为初始群体中最好染色体的运输成本, 为染色体对应的运输成本 ④遗传算子 选用最佳保留的轮盘赌复制法进行染色体的复制变异算子采用反转变异交叉算子用最大保留交叉, 其操作过程为: ( 1) 若染色体交叉点处的两个基因都为0, 则直接进行顺序交叉运算; ( 2) 若染色体交叉点处的基因不全为0, 则将交叉点左移( 右移) , 直到左右两个交叉处的基因都为0, 再进行顺序交叉运算 ⑤ 控制参数和算法的终止条件 采用自适应策略调整交叉率 和变异率[3] 由于遗传算法具有较大的随机性, 给定参数、X 、G, 使用以下算法终止条件: （1）若算法迭代到G 代, 则终止算法； （2）记录每代最佳染色体, 若某染色体连续保持最佳达到X 代, 可终止算法; （3）计算每代群体适应度均值, 若某代平均适应度和当代最佳染色体适应度的比值大于, 可终止算法。

⑥算法步骤（1）使用自然数编码方式, 构造表示可行行车线路的染色体; （2） 控制参数初始化( 交叉率、变异率和群体规模n , 正数M, 最大迭代次数G , 比值K, 最佳代数X ) ; （3） gen= 0, 随机产生初始群体P ( 0) , 群体中包括n 个染色体, 每个染色体表示一条行车线路; （4） i= 1; （5）将群体P ( gen) 中的第i 个染色体译为线路长度; （6）计算适应度; （7）若满足算法终止条件, 则停止, 否则继续; （8）i= i+ 1; （9）若i n, 则返回到（5） 否则转（10）; （10）根据适应度按轮盘赌法复制下一代染色体; （11）进行最大保留交叉、反转变异; （12）gen。