快递公司的配送数学建模

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

4、问题二的解答84.2.1对货运车辆数的估计84.2.2路线的规划8五、 模型的评价与改进105.1模型的优缺点分析105.2 模型的改进11六、参考文献11七、附录12一、问题重述某快递公司在某个地区拥有一支货运车队，每台货运车辆的载重量（吨）相同、平均速度（千米/小时）相同，该快递公司用这样的车为若干个客户配送物品，快递公司与客户以及客户与客户之间的公路里程（千米）为已知。每天，各客户所需物品的重量（吨）均已知，并且每个客户所需物品的重量都小于一台货运车辆的载重量，所有送货车辆都从快递公司出发，最后回到快递公司。快递公司每天的配送方案应当包括：当天出动多少台车？行驶路径如何？由此形成的当天总

5、运行里程是多少？一个合格的配送方案要求送货车辆必须在一定的时间范围内到达客户处，早到达将产生等待损失，迟到达将予以一定的惩罚；而一个好的配送方案还应该给出使配送费用最小或总运行里程最短的车辆调度方案。该快递公司希望你们：1. 建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法。2. 具体求解以下算例，并给出你们实际使用的软件名称、命令和编写的全部计算机源程序。算例载重量为 8 吨、平均速度为 60千米/小时 的送货车辆从快递公司（0）出发，为编号是 1，2，8 的8个客户配送物资。某日，第个客户所需物品的重量为吨（），在第个客户处卸货时间为小时，第个客户要求送货车辆到达的时间范围 由

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

7、2符号说明m 派出的货运车辆总数N 客户的数量Q 每台送货车的载重量 第i个客户与第j个客户之间的距离 第i个客户所需货品的重量v 每台送货车的平均速度 送货车从客户点i到客户点j所需要的时间 送货车到i的时间 送货车在客户点i卸货的时间 第i个客户要求送货车到达的时间范围的下限 第i个客户要求送货车到达的时间范围的上限三、问题分析 这是一个单配送中心、多客户点、非满载、带有时间窗的车辆配送路线问题（简称VRPTW）。问题的解决在于对一系列客户点，组织适当的行车路线，使货运车有序地通过它们，在满足一定的约束条件（各客户点货物需求量、交货时间、车辆载重限制等）下，达到总行程最短的目的。 问题一：

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

9、将具体数据代入模型，即可求出最短的路程方案。首先根据总配送量和运货车载重限制约束，求出送货运车派遣辆数。然后根据配送中心目标和客户点之间距离等，确定目标函数即最短行程模型。根据目标函数和时间窗约束，采用数学软件Lingo9.0编写程序，最终得出各货运车的行程线路。四、模型的建立与求解4.1问题一的解答4.1.1模型的准备为了安排路线，我们首先要对送货车的数量进行估计。约束条件越多，则安排线路越难，一辆车完成的任务越少，安排的车辆越多。我们可以按下述公式1估计所需货车的数量。其中，表示取整，a为参数，且0<a<1。约束条件越多，装卸越复杂，则a越小，表示一辆车所能容纳的货物越小。4.

10、1.2模型的建立先用0-1规划法定义以下变量： 模型I（硬时间窗的VRPTW问题）目标函数： (1) St： 模型I中，z表示行程式（1）：表示运货车总行程最短的目标式（2）：表示每个客户点有且仅有一辆车进入式（3）：表示每个客户点有且仅有一辆车离开式（4）：表示任务i只能由一辆车完成式（5）：表示每辆车的实际运载量不能超过它的容量式（6）（7）（8）：表示车均从配送中心出发，经过若干不重复的客户，最后重新回到配送中心式（9）（10）：表示送货车辆必须在时间范围内到达i客户点式（11）：i，j客户点间的运输时间由 时间=路程/速度 公式求得模型II（软时间窗的VRPTW问题）通过对题目“早到达

11、将产生等待损失，迟到达将予以一定的惩罚”的分析，车辆应该尽可能的在客户点要求的时间范围内到达，所以我们建立一个软时间模型，对于软时间模型，我们采用如下的转换将模型1中的约束条件（10）变成目标函数的一部分，同时取消对运货车到达的时间范围的限定。目标函数：St： 模型II中，p表示配送中心的送货成本 u表示运货车行驶一千米的成本 v表示送货车早到客户点单位时间所产生的损失 w表示送货车迟到客户点单位时间的惩罚配送公司的成本与运货车行驶的路程、早到产生的损失、迟到产生的惩罚有关。式（12）：表示配送公司成本最小的目标式（13）：表示每个客户点有且仅有一辆车进入式（14）：表示每个客户点有且仅有一辆

12、车离开式（15）：表示任务i只能由一辆车完成式（16）：表示每辆车的实际运载量不能超过它的容量式（17）（18）（19）：表示车均从配送中心出发，经过若干不重复的客户，最后重新回到配送中心式（20）：表示送货车辆到达j的时间=车到达i的时间+在i卸货的时间+i，j间行驶所需的时间式（21）：i，j客户点间的运输时间由 时间=路程/速度 公式求得4.1.3模型的求解求解车辆路径规划模型的方法有：禁忌法、模拟退火法、遗传算法和门槛接受法等。基于以上建立的模型，综合考虑各种算法后，我们选择使用遗传算法2对该模型进行求解。遗传算法的步骤如下：编码 采用自然数编码, 即序数编码。单车场非满载VRP 的一

13、条可行线路可编成长度为N+m的染色体, 其中 表示第k辆车完成的第n项任务。0 表示车场0, m 为完成任务所需要的车辆数。 产生初始群体 初始群体随机产生, 即产生N项货物运输任务点的全排列, 如, 若且, 将s 至N的基因逐一向后移动一位, 将0 插入到第s 位。接着, 若且, 如前操作, 使t 位空出, 插入0; 如此, 直到将m 个0 全部插入染色体为止。这样构成了一条初始染色体, 如此反复, 直到满足群体数。 适应度函数 适应度函数取, 其中 为染色体的适应度, b 为常数, 为初始群体中最好染色体的运输成本, 为染色体对应的运输成本。 遗传算子 选用最佳保留的轮盘赌复制法进行染色体

14、的复制。变异算子采用反转变异。交叉算子用最大保留交叉, 其操作过程为: ( 1) 若染色体交叉点处的两个基因都为0, 则直接进行顺序交叉运算; ( 2) 若染色体交叉点处的基因不全为0, 则将交叉点左移( 右移) , 直到左右两个交叉处的基因都为0, 再进行顺序交叉运算。 控制参数和算法的终止条件 采用自适应策略调整交叉率 和变异率3 。由于遗传算法具有较大的随机性, 给定参数、X 、G, 使用以下算法终止条件: （1）若算法迭代到G 代, 则终止算法； （2）记录每代最佳染色体, 若某染色体连续保持最佳达到X 代, 可终止算法; （3）计算每代群体适应度均值, 若某代平均适应度与当代最佳染色

15、体适应度的比值大于, 可终止算法。 算法步骤（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）根据适应度按轮盘赌法复制下

16、一代染色体; （11）进行最大保留交叉、反转变异; （12）gen= gen+ 1; （13）若满足算法终止条件, 则停止, 否则转（4）。 （14）若算法终止时, 得到的目标函数值大于M , 则得不到可行解, 说明车辆数不够, 需减小a , 重新估计m, 转（1）重新运行,直到得到满意解。 4.2问题二的解答4.2.1对货运车辆数的估计 我们取为0.95，此时求得m=3，所以估计派出的车辆为3辆。4.2.2路线的规划 Error! Reference source not found.简明的表示出快递公司与客户点间、客户点间的距离，每个客户的需求，货运车在每个客户点卸货的时间以及每个客户点要

17、求的送货时间范围距离 0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000需求（q）21.54.531.542.532卸货时间（s）121322.530.81时间范围1, 44, 61, 24, 73, 5.52, 55, 81.5, 41, 4表格 1

18、还已知Q=8，v=60，N=8，m=3由此建立目标函数和约束条件目标函数：St：利用Lingo软件求解该数学模型（程序见附录）得解：派出3辆车； 行驶路径：0->3- 1- >2- >0 0- >6- >4- >0 0- >8- >5- >7- >0运行总里程：910千米 行程规划示意图：5、 模型的评价与改进5.1模型的优缺点分析优点：一、考虑全面：通过讨论客户对送货车辆的到达是否有严格的时间限制，分别建立带软时间窗和硬时间窗的两个模型。同时，考虑到软时间窗的成本问题，创新性的将惩罚及损失之和作为目标函数的一部分，保证了在行程最短的

19、情况下配送成本不会较高。二、约束条件完整：每个约束条件都与题目的内容一一对应，且比较清楚的在论文中对每个式子的意义做了阐述。三、遗传算法的应用：利用遗传算法解决车辆路径规划问题，有广泛的适应性与灵活性。缺点：1、 值的不同会影响估计出来的车辆数，仅用一种值来确定车辆数目局限性很大。 二、模型具有局限性：只适用于客户点数较小且配送中心单一、送货车型号相同的情况。5.2 模型的改进根据估算车辆数目的公式：对进行多次赋值。在保证车辆数目大于3辆（Q=8，）的前提下，寻找接近于m的值，并带入模型，将求出的解与m=3时求得的结果进行对比，得到使行程最短的配送方案。六、参考文献1中南大学，物流车辆调度问题

20、研究，2朱树人 李文彬 匡芳君，一种带软时间窗的物流配送优化遗传算法，计算机工程与科学，27（12）,108-110,20073胡一萍 徐海，一种基于粗糙集的模糊数学形态学方法J，数据采集与处理，17（3），333-3364李军 谢秉磊 郭耀煌，非满载车辆调度问题的遗传算法，系统工程理论与方法应用，9（3）,235-239,20005周屹 李海龙 王锐，遗传算法求解物流配送中带时间窗的VRP问题，吉林大学学报（理学版），46（2）,300-303,2008 6阎庆 邰蕾蕾，用混合遗传算法解决有时间窗的车辆路径规划为题，安徽大学学报（自然科学版），31（2）,41-44,20077邹彤 李宁 孙

21、德宝，不确定车辆数的有时间窗的车辆路径问题的遗传算法，系统工程理论与实践，第6期，134-138,2004 8张钦 李辉，带有时间窗约束的车辆路径问题的一种改进遗传算法，系统管理学报，19（5）,589-592,2010 9供应链网络物流配送与车辆路径问题，七、附录1、表1客户12345678（吨）21.54.531.542.53（小时）121322.530.81, 44, 61, 24, 73, 5.52, 55, 81.5, 42、表2 01234567800406075902001001608014006540100507511010026065075100100757575375407

22、50100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000 3、 有关程序 MODEL:SETS: points/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

23、; 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 100 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.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