快递公司的配送数学建模

1、快递公司的配送问题摘要 配送是物流系统中非常重要的一个环节，在物流的各项成本中，配送成本占了相当高的比例，减少配送里程以降低物流配送成本成为物流管理过程中首要考虑的问题之一。本文在已知货运车容量、各客户所需货物重量、快递公司与客户以及客户与客户之间的距离的条件下，建立了以单车场路径问题模型（即VRP模型）为基础、以车辆总行程最短为目标函数、以货物运输量小于汽车载重量以及在客户要求的时间范围内运送货物等为约束条件的单目标线性规划模型。 对于问题一，本文建立了两个模型：模型I：硬时间窗车辆路径规划模型 首先根据题目所给条件，对运货所需的车辆数进行预估，然后结合货物运输量小于汽车载重量、一个客户点的

2、货物仅由一辆车配送等约束条件，同时考虑线路的连通性和汽车到达客户点的时间范围，采用0-1规划法建立使总运行里程最小的车辆路径规划模型。 模型II：软时间窗车辆路径规划模型在模型I硬时间窗车辆路径规划模型的基础上，将模型I中的关于时间范围的约束条件，通过设定惩罚函数的系数，变成目标函数的一部分。本文在考虑路程最短的目标的同时，也要求尽可能在时间范围内到达。因此，建立了以成本（包括惩罚成本以及行驶过程中带来的成本）最小为目标的函数，以运输量小于汽车载重量以及线路的连通性等为约束条件，建立软时间车辆路径规划模型。最后运用遗传算法求解模型。对于问题二，根据题目所提供的数据，利用硬时间窗车辆路径规划模型

3、。首先，根据货运车的载重量和客户点的需求总量，估计出运货所需车辆数为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模型的优缺点分

4、析105.2 模型的改进11六、参考文献11七、附录12一、问题重述某快递公司在某个地区拥有一支货运车队，每台货运车辆的载重量（吨）相同、平均速度（千米/小时）相同，该快递公司用这样的车为若干个客户配送物品，快递公司与客户以及客户与客户之间的公路里程（千米）为已知。每天，各客户所需物品的重量（吨）均已知，并且每个客户所需物品的重量都小于一台货运车辆的载重量，所有送货车辆都从快递公司出发，最后回到快递公司。快递公司每天的配送方案应当包括：当天出动多少台车？行驶路径如何？由此形成的当天总运行里程是多少？一个合格的配送方案要求送货车辆必须在一定的时间范围内到达客户处，早到达将产生等待损失，迟到达将予

5、以一定的惩罚；而一个好的配送方案还应该给出使配送费用最小或总运行里程最短的车辆调度方案。该快递公司希望你们：1. 建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法。2. 具体求解以下算例，并给出你们实际使用的软件名称、命令和编写的全部计算机源程序。算例载重量为 8 吨、平均速度为 60千米/小时 的送货车辆从快递公司（0）出发，为编号是 1，2，8 的8个客户配送物资。某日，第个客户所需物品的重量为吨（），在第个客户处卸货时间为小时，第个客户要求送货车辆到达的时间范围 由表1给出。快递公司与各客户以及各客户间的公路里程（单位：千米）由表2给出。问当日如何安排送货车辆（包括出动车辆的

6、台数以及每一台车辆的具体行驶路径）才能使总运行里程最短。 二、模型假设和符号说明2.1模型假设1、所有的货运车辆都没有超载。2、 快递公司能提供充足的货运车辆。3、 一个客户点只有一辆货运车进入和离开。4、 每条配送路径都在货运车辆的配送范围内。5、 同一个客户所需要的物品只由一辆货运车配送。6、 不考虑货物的类型和货运车的车型，货物可混装。7、 不考虑货运车速度及运输时间因天气、交通等因素的影响。8、 快递公司与客户以及客户与客户之间的距离、每天各客户所需物品的重量均视为不变。2.2符号说明m 派出的货运车辆总数N 客户的数量Q 每台送货车的载重量 第i个客户与第j个客户之间的距离 第i个客

7、户所需货品的重量v 每台送货车的平均速度 送货车从客户点i到客户点j所需要的时间 送货车到i的时间 送货车在客户点i卸货的时间 第i个客户要求送货车到达的时间范围的下限 第i个客户要求送货车到达的时间范围的上限三、问题分析 这是一个单配送中心、多客户点、非满载、带有时间窗的车辆配送路线问题（简称VRPTW）。问题的解决在于对一系列客户点，组织适当的行车路线，使货运车有序地通过它们，在满足一定的约束条件（各客户点货物需求量、交货时间、车辆载重限制等）下，达到总行程最短的目的。 问题一：题目要求建立送货车辆每天总运行里程最短的一般数学模型。因为问题要求制定的配送方案与车辆数目和时间（包括：卸货时间

8、和送货途中所需时间）有关，所以,首先对运货所需的车辆数进行预估。通过讨论时间窗口是硬窗口还是软窗口，本题分别建立了两个数学模型。对于硬窗口的VRPTW问题，送货车必须在给定的时间范围内到达客户点，所以加入对每辆运货车到达客户点的时间限制，综合求出总里程数最短的路线。而对于软窗口的VRPTW问题，没有严格的时间限制。但是，货车早到或晚到产生的损失和惩罚会对配送公司的成本产生影响，所以，配送方案应该保证车辆行驶里程最短，且尽可能的在客户点要求的时间范围内到达。 问题二：基于问题一的模型，将具体数据代入模型，即可求出最短的路程方案。首先根据总配送量和运货车载重限制约束，求出送货运车派遣辆数。然后根据

9、配送中心目标和客户点之间距离等，确定目标函数即最短行程模型。根据目标函数和时间窗约束，采用数学软件Lingo9.0编写程序，最终得出各货运车的行程线路。四、模型的建立与求解4.1问题一的解答4.1.1模型的准备为了安排路线，我们首先要对送货车的数量进行估计。约束条件越多，则安排线路越难，一辆车完成的任务越少，安排的车辆越多。我们可以按下述公式1估计所需货车的数量。其中，表示取整，a为参数，且0a3- 1- 2- 0 0- 6- 4- 0 0- 8- 5- 7- 0运行总里程：910千米 行程规划示意图：5、 模型的评价与改进5.1模型的优缺点分析优点：一、考虑全面：通过讨论客户对送货车辆的到达

10、是否有严格的时间限制，分别建立带软时间窗和硬时间窗的两个模型。同时，考虑到软时间窗的成本问题，创新性的将惩罚及损失之和作为目标函数的一部分，保证了在行程最短的情况下配送成本不会较高。二、约束条件完整：每个约束条件都与题目的内容一一对应，且比较清楚的在论文中对每个式子的意义做了阐述。三、遗传算法的应用：利用遗传算法解决车辆路径规划问题，有广泛的适应性与灵活性。缺点：1、 值的不同会影响估计出来的车辆数，仅用一种值来确定车辆数目局限性很大。 二、模型具有局限性：只适用于客户点数较小且配送中心单一、送货车型号相同的情况。5.2 模型的改进根据估算车辆数目的公式：对进行多次赋值。在保证车辆数目大于3辆

11、（Q=8，）的前提下，寻找接近于m的值，并带入模型，将求出的解与m=3时求得的结果进行对比，得到使行程最短的配送方案。六、参考文献1中南大学，物流车辆调度问题研究，/p-.html，2013.8.72朱树人 李文彬 匡芳君，一种带软时间窗的物流配送优化遗传算法，计算机工程与科学，27（12）,108-110,20073胡一萍 徐海，一种基于粗糙集的模糊数学形态学方法J，数据采集与处理，17（3），333-3364李军 谢秉磊 郭耀煌，非满载车辆调度问题的遗传算法，系统工程理论与方法应用，9（3）,235-239,20005周屹 李海龙 王锐，遗传算法求解物

12、流配送中带时间窗的VRP问题，吉林大学学报（理学版），46（2）,300-303,2008 6阎庆 邰蕾蕾，用混合遗传算法解决有时间窗的车辆路径规划为题，安徽大学学报（自然科学版），31（2）,41-44,20077邹彤 李宁 孙德宝，不确定车辆数的有时间窗的车辆路径问题的遗传算法，系统工程理论与实践，第6期，134-138,2004 8张钦 李辉，带有时间窗约束的车辆路径问题的一种改进遗传算法，系统管理学报，19（5）,589-592,2010 9供应链网络物流配送与车辆路径问题，/p-.html ，2013.8.7七、附录1、表1客户12345678（

13、吨）21.54.531.542.53（小时）121322.530.81, 44, 61, 24, 73, 5.52, 55, 81.5, 42、表2 0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000 3、 有关程序 MODEL:SETS: point

14、s/0,1,2,3,4,5,6,7,8/:f; point_aim/1,2,3,4,5,6,7,8/:timea,timeb,q,s; roads(points,points):d,x1,time_between; cars/1.3/; reach/1 2 3 4 5 6 7 8/:time_reach; road_car(roads,cars):x; task_car(points,cars):y; task_aim(point_aim,cars):y1;ENDSETSDATA:d=0 40 60 75 90 200 100 160 80 40 0 65 40 100 50 75 110 1

15、00 60 65 0 75 100 100 75 75 75 75 40 75 0 100 50 90 90 150 90 100 100 100 0 100 75 75 100 200 50 100 50 100 0 70 90 75 100 75 75 90 75 70 0 70 100 160 110 75 90 75 90 70 0 100 80 100 75 150 100 75 100 100 0;m=3;timea=1 4 1 4 3 2 5 1.5;timeb=4 6 2 7 5.5 2.5 8 4;q=2 1.5 4.5 3 1.5 4 2.5 3;s=1 2 1 3 2 2

16、.5 3 0.8;capacity=8;time_between=0 0.8 1.2 1.5 1.8 4 2 3.2 1.6 0.8 0 1.3 0.8 2 1 1.5 2.2 2 1.2 1.3 0 1.5 2 2 1.5 1.5 1.5 1.5 0.8 1.5 0 2 1 1.8 1.8 3 1.8 2 2 2 0 2 1.5 1.5 2 4 1 2 1 2 0 1.4 1.8 1.5 2 1.5 1.5 1.8 1.5 1.4 0 1.4 2 3.2 2.2 1.5 1.8 1.5 1.8 1.4 0 2 1.6 2 1.5 3 2 1.5 2 2 0;ENDDATAmin=sum(roads(i,j):d(i,j)*sum(cars(k):x(i,j,k);for(road_car:bin(x);for(task_car:bin(y);for(task_