论文--快递公司送货优化策略

1、快递公司送货优化策略王振坤指导教师：晏兴学（河西学院数学与统计学院甘肃张掖734000 ）摘要：本论文对快递公司送货策略问题进行了优化，建立了数学模型。我们针对题干所提 出的问题，给该公司提供了一个合理的送货策略；针对在一些特殊条件下的限制，我们也 给该公司提出了一个费用最省的策略。关键词：点临最近法matlab距离矩阵0-1整数线性规划express company delivery optimization strategywangzhenkunteacher： yanxingxue(hexi universitymathematics and statistics institute g

2、ansu zhang ye 734000) abstract: this paper express company delivery strategy to optimize the problem, a mathematical model is set up. we do for questions proposed, to the company provides a reason able delivery strategy; i n some special conditi ons to the limit, we also give the compa ny proposed a

3、 fee of the provi nee of the st rat eg y.key words: a recent law in the distanee matrix matlab 0-1 integer linear programming快递公司送货策略。目前，快递行业正蓬勃发展，为我们的生活带來更多 方使。一般地，所有快件到达某地后，集中存放在总部，然后由业务员分别进 行派送；对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须 有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。假定 所有快件在早上7点钟到达，早上9点钟开始派送，要求与当天17点z前必须 派

4、送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的 时间为10分钟，途中速度为25km/h,每次出发最多能带25千克的重量。为了 计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克, 公司总部位于坐标原点，每个送货点的位置和快件重量如下表所示，并且假设 街道平行于坐标轴方向。1. 请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（需 耍多少业务员，每个业务员的运行线路，以及总的运行公里数）。2. 如果业务员负重时的速度是20km/h,获得酬金是3元/km*kg；而不携 带快件时的速度是30km/h,酬金是2元/km,请为公司设计一个费用最省的策

5、略。(送货点快件量t坐标(km)送货点快件量t坐标(km)送货点快件量t坐标(km)送货点快件量t坐标(km)xyxy1832163.521628.215175.86183654187.5111745. 547197.815126308153.419954. 5311326.222577.279226.821082. 396232.427991.4102247.61519106. 5140259.61514114. 1173261020171212. 714627122113135.8129286.02420143.81012298. 12516204.6714304.22818本问题是一个关

6、于快递公司送货策略的实际问题，对于快递公司，他们的 任务是在指定的时间内将快件运到指定的地点，而快件一般先是集中的放在某 地，然后由快递公司的业务员去运送，因此，如何在能够按时按地完成任务的 情况下聘用最少的业务员是快递公司所最关心的问题。一问题分析(1) 快递公司一般将收到的快件集中放到总部，然后由业务员进行派送， 派送地点已经明确。每个业务员工作的平均时间不超过6小时，并且一个业务 员每次出发所携带快件的重量不能超过25kg。公司为了节约成本，必须要用最 少的人在规定的时间内把所有的快递送到客户家屮，因此选择什么样的派送路 线和派遣多少业务员得尤为重要。本论文试图从最优化的角度，建立起满足

7、快 递公司选择恰当数量业务员的数学模型，借助计算机的高速运算能力和逻辑判 断能力，求出公司派遣的业务员数量和业务员的送货路线。(2) 不妨我们假定快件在早上7点钟到达，早上9点钟开始派送，要求于 当天17点之前必须派送完毕，每个业务员每天平均工作不超过6小时，在侮个 送货点停留的时间为10分钟，途中速度为25km/h,每次出发最多能带25千克 的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量 为184.5千克，公司总部位于坐标原点，每个送货点的位置和快件的重量如下 表所示，并且假设街道平行于坐标轴方向。为了分析问题方便，首先建立坐标系。以快递公司的总部作为原点o,过 原点的

8、水平线0x作为x轴的正方向，过原点垂直于x轴指向正前方的水平线 0y作为y轴建立高斯平面直角坐标系。何:个客户所在地用一个点表示点的横 纵坐标之和表示公司和客户所在地之间的距离。（如图）t/kn.2015 20号24号 18号2s号30号 26号.29号27号 14号10 13号 12号2号小号10号101515号.23号.32号22号1一_1_1一11一111- x/km2025%1. 模型假设1. 假设每个人的路线一旦确定，再不更改每次业务员从一个区送货回来,再配货的时间为0,即不花时间。2. 送货期间，每个人相互z间互不影响业务员不会发生意外，即不会意外 的花一些时间，业务员中途不休息。

9、3. 业务员在总部装快件的时间不予考虑，即业务员在一次运完快件后，再 次去总部装快件的时间为零且业务员走的路都为横纵坐标。4. 如果离某一点最近的点不止一个，这时我们要从快件的量出发，选取加 上此快件量最接近25千克而不能超过25千克的0的地。5. 送货员在任意两点间的送货距离为任意两点间横纵坐标差的和。6. 业务员在中途除了送货z外没有别的时间耽搁。%1. 符号说明从i点是否到j点，是则设为1,否设为0；兀（）-从k点是否到°点，是则设为1,否设为0；y“一i点与j点是否同纽.，是则设为1,否设为0；%从i点到j点的总负重量；d”-i点与j点之间的距离；q第i点的邮件量；%1. 模

10、型建立与分析1模型一的建立与求解对于问题一的解决，我们分两步來完成，首先将30个点进行分组，使每组 总的邮件数之和尽量接近25kg,即一个邮递员的最人载重量。分组时我们采用 先找两个可行解，然后将两可行解比较拟合得到最优解的方法。其次，确立组 数之后求每组最优路线，通过计算时间，将邮递员分到相应的组内。2确定每条路线所经过的目的地i点与点为一组 ，点不与笊一组首先将30点进行分组使每组的总邮件数尽量接近25kg,而不超过25kgo 于是我们建立以下模型：11i点的下一点是点：=s"0 从点不到点30 mincj»_25 i=o30 匸凶< 25 i=03030 30工

11、 1 / 6儿 + 工工 d.x. y./25<6 /=0/=0 j=07=030 30心 0(我们安排了8条运送路线)最后我们用matlab软件解出了结果：0-1-3-4-50-2-6-7-130-8-9-10-120-18-26-280-11-15-22-23-320-19-24-250-14-16-17-20 0-27-29-303确定每条路线上经过目的地的先后次序由于每个邮递员都是从0点出发再回到0点，于是我们想到了用tsp算法 解闭回路最优路线问题，通过matlab编程我们得到八条最优路线，经计算得到 总路程及相应的时间：送货路线耗时(h)行程(km)0134501.95320

12、2137602. 3542010128902. 3542018262804. 0288019252403.226801617201402.9156027293004. 18924送货员员的确立通过时间及路程的计算我们指派五名邮递员，在总时间不超过6小时的前 提下，使五名邮递员耗时及行程尽屋均衡，路程近的我们派一人送两次，远的邮递员只送一次即可，通过计算比较我们得到最终结果:业务员送货路线耗时(h)行程(km)业务员一0134501.95320223223151103. 7272业务员二02137602. 3542019252403. 2268业务贝一010128902. 35420161720

13、1402.9156业务员四018262804. 0288业务员五027293004. 18925模型二的建立与求解对于模型二我们利用模型一的分组及最优路线，在此基础上考虑费用最少 原则，均衡时间、行程及费用再确立邮递员数。在计算费用的过程中我们发现在一条线路上邮递员每到一个点都会卸下相 应的邮件，从而使负重数减少，即每过一点计算费用就会改变。总的费用为负重时的费用与徒步时的费用，用表示负重量，每过一站©会相应改变，即勺使变量。我们的约束条件为每组总件数不超过25kg，除原点外每点只进出一次，每组总时间不超过6小时。冃标函数如下：min工3勺d內+工2“血0ik通过matlab编程算出

14、每条路线的费用，分别为：第1条回路为：013450时间为：2. 0333h花费为：767.5元；第2条回路为：0213760时间为:2. 6333h花费为:1396. 6元;第3条回路为：01012890时间为：2. 5667h花费为:1357.5 元；第4条冋路为:0161720140时间为:3. lh花费为:1438. 4元； 第5条冋路为：022322315110时间为：4. lh花费为：2318.2元;第6条冋路为：01925240时间为：3. 3333h花费为：2310.2元; 第7条冋路为：01826280时间为：4. 1667h花费为：2620元；第8条冋路为：02729300时

15、间为：4. 3333h花费为：2891.9元; 这八条路线的总时间为：26. 2667h总费用为:15100.3元 总路程为：492km。%1. 结果分析通过以上模型我们解决了快递公司在实际中所面临的送货员聘用问题，对 于问题一，我们以运送总距离最短目标函数建立01规划数学模型。我们先将 木问题简化为在不考虑时间约束的情况下一个业务员完成任务所经过的每条送 货路线，这也就是我们对于问题一所需要找出的送货路线，对于送货路线的确 定我们主要分两步进行，我们通过点临最近法一一在满足约束条件的前提下， 在一次运送过程中，下一个目标点的确定要离上一个目标点最近。寻找出了每 条路线所经过的日的地；对于经过

16、这些日的地的先后顺序我们采用tsp算法， 找出经过它们的最短路，确定他们的先后顺序。经过我们的计算，我们求得一 个人完成任务的运送路线为8条，我们又考虑了业务员工作时间的要求，求出 了完成任务所需更的最少业务员为5人，最短总路程为492km,每个业务员的 行走路线分别如下：业务员送货路线耗时(h)行程(km)业务员一0134501.95320223223151103. 7272业务员二02137602. 3542019252403. 2268业务员三010128902. 354201617201402.9156业务员四018262804. 0288业务员五027293004. 1892对于问题

17、二，我们借助于在问题一求解出路线的基础上，以费用最省为目 标函数建立数学模型。出于问题二增加了约束条件，但是对于问题一求解出的 总距离最小的线路是不变的，所以我们只需在满足时间耍求的条件下对业务员 的送货线路进行调整而不改变总的送货线路。于是我们求得问题二的最省费用 为15100.3元，送货员安排如下：业务员送货路线耗时(h)行程(km)业务员一0134502.0432019252403. 3468业务员二02137602.6442010128902.442业务员三01617201403. 1156业务员四0 22 32 231511 04. 1172业务员五018262804. 1788业务

18、员六027293004. 3492我们帮他们找出了聘用的最少送货员人数，以及每个送货员运送路线的安 排，线路的产生是我们通过对实际问题中可能遇到的结果进行比较，从中选择 出了最优结果。对于从最近点开始送货我们求出的最短路程是492km,而从最 远点开始送货的最短路是518km,于是我们选择了从最近点运送的方案。对于问题一和问题二的分析，我们可以将问题二看成是问题一约束条件的 増加，问题一的结果适用于问题二，只是因需耍满足时间要求而进行调整。木问题的求解具有一般性，对实际问题的解决具有一定的指导意义。六模型评价与推广1木模型的优点：木论文根据问题要求利用优化的思想，先将问题简化，然后再增加约束条 件，一步一步地对模型进行完善，使所建立的模型满足题冃所给出的约束条件, 使解决的问题最大限度的接近实际问题。本论文建立的模型具有一般性，是将 现实问题屮可能出现的情况通过求解比较，从屮选择出最优的方案。本论文模 型的建立从实际问题出发，对于解决其它问题也具有一定的实用性，具有较强 的推广价值。2本模型的缺点：本模型求解复杂程度太人，当送货点个数增加一个，求解复朵度就会成级 数增加，由于受