快递公司的配送数学建模

快递公司的配送问题摘要配送是物流系统中非常重要的一个环节，在物流的各项成本中，配送成本占了相当高的比例，减少配送里程以降低物流配送成本成为物流管理过程中首要考虑的问题之一。本文在已知货运车容量、各客户所需货物重量、快递公司与客户以及客户与客户之间的距离的条件下，建立了以单车场路径问题模型（即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规划法Lingo1目录一、问题重述............................................................................................................................2二、模型假设和符号说明........................................................................................................2三、问题分析............................................................................................................................3四、模型的建立与求解............................................................................................................44.1问题一的解答..............................................................................................................44.1.1模型的准备.......................................................................................................44.1.2模型的建立.......................................................................................................44.1.3模型的求解.......................................................................................................74.2问题二的解答..............................................................................................................84.2.1对货运车辆数的估计.......................................................................................84.2.2路线的规划.......................................................................................................8五、模型的评价与改进........................................................................................................115.1模型的优缺点分析....................................................................................................115.2模型的改进...............................................................................................................12六、参考文献..........................................................................................................................12七、附录..................................................................................................................................132一、问题重述某快递公司在某个地区拥有一支货运车队，每台货运车辆的载重量（吨）相同、平均速度（千米/小时）相同，该快递公司用这样的车为若干个客户配送物品，快递公司与客户以及客户与客户之间的公路里程（千米）为已知。每天，各客户所需物品的重量（吨）均已知，并且每个客户所需物品的重量都小于一台货运车辆的载重量，所有送货车辆都从快递公司出发，最后回到快递公司。快递公司每天的配送方案应当包括：当天出动多少台车？行驶路径如何？由此形成的当天总运行里程是多少？一个合格的配送方案要求送货车辆必须在一定的时间范围内到达客户处，早到达将产生等待损失，迟到达将予以一定的惩罚；而一个好的配送方案还应该给出使配送费用最小或总运行里程最短的车辆调度方案。该快递公司希望你们：1.建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法。2.具体求解以下算例，并给出你们实际使用的软件名称、命令和编写的全部计算机源程序。〔算例〕载重量为Q8吨、平均速度为v60千米/小时的送货车辆从快递公司（i0）出发，为编号是i1，2，…，8的8个客户配送物资。某日，第i个客户所需物品的重量为iq吨（iqQ），在第i个客户处卸货时间为is小时，第i个客户要求送货车辆到达的时间范围,iiab由表1给出。快递公司与各客户以及各客户间的公路里程（单位：千米）由表2给出。问当日如何安排送货车辆（包括出动车辆的台数以及每一台车辆的具体行驶路径）才能使总运行里程最短。二、模型假设和符号说明2.1模型假设1、所有的货运车辆都没有超载。2、快递公司能提供充足的货运车辆。3、一个客户点只有一辆货运车进入和离开。4、每条配送路径都在货运车辆的配送范围内。5、同一个客户所需要的物品只由一辆货运车配送。6、不考虑货物的类型和货运车的车型，货物可混装。7、不考虑货运车速度及运输时间因天气、交通等因素的影响。8、快递公司与客户以及客户与客户之间的距离、每天各客户所需物品的重量均视为不变。32.2符号说明m派出的货运车辆总数N客户的数量Q每台送货车的载重量ijc第i个客户与第j个客户之间的距离iq第i个客户所需货品的重量v每台送货车的平均速度ijt送货车从客户点i到客户点j所需要的时间it送货车到i的时间is送货车在客户点i卸货的时间ia第i个客户要求送货车到达的时间范围的下限ib第i个客户要求送货车到达的时间范围的上限三、问题分析这是一个单配送中心、多客户点、非满载、带有时间窗的车辆配送路线问题（简称VRPTW）。问题的解决在于对一系列客户点，组织适当的行车路线，使货运车有序地通过它们，在满足一定的约束条件（各客户点货物需求量、交货时间、车辆载重限制等）下，达到总行程最短的目的。问题一：题目要求建立送货车辆每天总运行里程最短的一般数学模型。因为问题要求制定的配送方案与车辆数目和时间（包括：卸货时间和送货途中所需时间）有关，所以,首先对运货所需的车辆数进行预估。通过讨论时间窗口是硬窗口还是软窗口，本题分别建立了两个数学模型。对于硬窗口的VRPTW问题，送货车必须在给定的时间范围内到达客户点，所以加入对每辆运货车到达客户点的时间限制，综合求出总里程数最短的路线。而对于软窗口的VRPTW问题，没有严格的时间限制。但是，货车早到或晚到产生的损失和惩罚会对配送公司的成本产生影响，所以，配送方案应该保证车辆行驶里程最短，且尽可能的在客户点要求的时间范围内到达。问题二：基于问题一的模型，将具体数据代入模型，即可求出最短的路程方案。首先根据总配送量和运货车载重限制约束，求出送货运车派遣辆数。然后根据配送中心目标和客户点之间距离等，确定目标函数即最短行程模型。根据目标函数和时间窗约束，采用数学软件Lingo9.0编写程序，最终得出各货运车的行程线路。4四、模型的建立与求解4.1问题一的解答4.1.1模型的准备为了安排路线，我们首先要对送货车的数量进行估计。约束条件越多，则安排线路越难，一辆车完成的任务越少，安排的车辆越多。我们可以按下述公式[1]估计所需货车的数量。1qm1iiQN其中，表示取整，a为参数，且0a1。约束条件越多，装卸越复杂，则a越小，表示一辆车所能容纳的货物越小。4.1.2模型的建立先用0-1规划法定义以下变量：否则后访问需求点访问需求点车辆jik01ijkx否则配送的货物有客户ki01yik模型I（硬时间窗的VRPTW问题）目标函数：m1k1i1jijkijxczinNNM(1)5St：）（）（）（）（）（）（）（）（）（）（）（）（））（，（））（，（11vct10bta9ttst8...2,1k1x7...2,1k/...2,1h0x-x6...2,1k1x5...2,1kyq4)...2,1i(13...21i1x2...21j1xijijiikijijii1ik0i1i1jhjkihj1jjk01iiki11j1ijk1i1ijkNNNNNmkikNmkNmkmmNmmQNyNN模型I中，z表示行程式（1）：表示运货车总行程最短的目标式（2）：表示每个客户点有且仅有一辆车进入式（3）：表示每个客户点有且仅有一辆车离开式（4）：表示任务i只能由一辆车完成式（5）：表示每辆车的实际运载量不能超过它的容量式（6）（7）（8）：表示车均从配送中心出发，经过若干不重复的客户，最后重新回到配送中心式（9）（