快递公司送货策略 8页

快递公司送货策略摘要快递是快递公司快速收集、运输和递送客户文件、物品或货物的一种服务.合理选择送货线路并制定业务员分派方案是极其重要的，它不仅可以加快配送速度，提高服务质量,还可以有效的降低配送成本，增加经济效益.本文是关于快递公司送货策略的优化设计问题，即在给定送货地点和给定设计规划的前提下，确定所需的业务员人数，每个业务员的行程路线，总的运行公里数及费用最省的策略对此,本文重点讨论的问题是快递公司如何雇佣多少业务员送货，如何确定每个业务员的运行线路以达到费用最省的目的在问题一中，由于不要考虑业务员费用，所以我们以业务员所走路程最短为目标函数.N k-\而n[Z盘R+/R+doR]7=1m=l Jmj\jk先假定将送货点划分为N个区域，然后用LINGO软件进行求解，得出最短送货距离，然后引入路径矩阵D,用MATLAB编程求解得出业务员的最佳行走路径及所需要的业务员个数5人在问题二中，主要考虑业务员的费用，通过对载货费用与空载费用求和得到所需总费用所以，我们以总费用最小为目标建立动态规划模型N k m-1盘+oR GRj+2d min£3・Z£R.m QR7=1〃+l jl」m=l n=\J jk通过运用LINGO和MATLAB软件求解得出最优送货路线及送货费用在问题三中，我们沿用问题一的模型，并将其中每趟送货不超过6个小时的约束条件改为不超过8个小时，得出最有送货路线及业务员人数4人关键字路程矩阵动态规划遗传算法

一、问题重述目前，快递行业正蓬勃发展，为我们的生活带来更多方便一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送;对于快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货,但是，太多的业务员意味着更多的派送费用假定所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h,每次出发最多能带25千克的重量为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为

184.5千克，公司总部位于坐标原点处（如图2）,每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行于坐标轴的折线

（1）请你运用有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；

（2）如果业务员携带快件时的速度是20km/h,获得酬金3元/knvkg；而不携带快件时的速度是30km/h,酬金2元/km,请为公司设计一个费用最省的策略；

（3）如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？

二、问题假设与符号说明

2.1模型的假设假设L每天每个送货点只由一个业务员送一次货假设2业务员在送货区域内只走最短路径假设3各个业务员相互独立，互不影响假设4送货运行路线均为平行于坐标轴的折线假设5各业务员在中途除了送货之外没有其它时间耽搁

2.2符号说明符号符号说明用

0、1表示第i个送货点是否属于第j个送货区・・wIJG•I第i个送货点的邮件+重量两送货点之间的最短折线距离dmnRjm第j个送货区内的k个送货点之间的有序线路解集表示原点和第j个送货区内第一个送货点之间的距离d°RdoR»表示原点和第j个送货区内最后一个送货点之间的距离JkjD路径矩阵

三、问题分析此题是一个典型的中国邮递员问题，要求我们根据各种约束条件为快递公司建立出比较合理的送货策略针对问题一要求我们根据时间和重量等方面的约束来建立一个合理的邮件配送模型模型以邮递员数量最少且送货总距离最小为最佳送货策略考虑到送货时间由送货行驶距离和行驶速度来决定（送货点个数和位置确定的情况下），所以当送货所需的总行驶距离为最小时，所需的送货时间和所需的邮递员个数都将最少因此我们考虑建立以送货总行驶距离最小为目标函数的数学模型以此为基础将送货点分到若干区内，然后确定由多少邮递员分别给哪几个区送货针对问题二此问给出了具体的运输费用，要求我们求解费用最省的送货策略，因此我们根据运费和送货行程的关系建立费用最省模型，并结合各种约束条件来计算求解针对问题三此问即在问题一的基础上将约束条件中每个业务员平均每天的工作时间从不超过6个小时改为了不超过8个小时，因此我们可以沿用第一问的模型，改变时间约束条件来进行求解计算

四、模型的建立与求解问题一建立一个合理的送货模型

（一）模型分析建立此间要求我们根据时间和重量等方面的约束来建立一个合理的邮件配送模型当邮递员数量最少且送货总距离最小时可得到比较合理的送货策略当送货所需的总行驶距离为最小时，所需的送货时间和所需的邮递员都将最少因此我们考虑建立以送货总行驶距离最小为目标函数的数学模型为了得到简化的数学模型，我们首先假定将所有送货点分为N个送货区，在最优化总体送货总距离的基础上为N个送货区分得一些送货点，并得出此区域内的送货具体线路（即顺序），然后再根据时间的约束为每位邮递员分配送货区域，以此来得到一个较优的合理的送货方案先设立如下变量W表示第i个送货点不属于第j个送货区咒:J一表示第i个送货点属于第j个送货区第j个送货区内的k个送货点之间的有序线路解集Rim或〃两送货点之间的最短折线距离G#第i个送货点的邮件重量以总行驶距离最小为目标函数.N k-\而R.+△+10^]Z/ZG/R j=\m=l jmj\jk约束条件每天每个送货点只由一个邮递员送一次货NX%=11=

123...30j=i J每个送货区的送货点个数等于相应的值k30X w-.=k-j=

123...30M lJ J每个邮递员每次出发带邮件不超过25千克30E W..G.25j=l

23...30Z=1每趟送货不能超过小时:6k—\301£3R R+dR+dR工1・%.+但~~”——八---------------------L6i=\6J25二模型求解1定义路径矩阵由于有序解集R的难以确定性，为了方便求解我们引入一新变量路径矩阵D设k*k的矩阵D是所求的一条解路径，它满足每行每列有且仅有一个元素为1,其余为0亿=1表示路径中存在从送货点G.到送货点j的边与，显然，当，=时必有亿/=0这是一种基于边的路径编码方法，如图1a所示的矩阵是四个送货点的一个解，它表示如图1b所示的一条解路径0010100000010100a b图1因此可由路径矩阵D得到有序解集R当矩阵D满足亿=4=

1...〃+4=

1..・时可得到唯一的有序解集R E.2〃+d..]其中eR=j,k.i.j.k..n,n+d..N2确定算法送货路径问题是物流送的核心问题，对于此类多变量，多可行性的问题，一般难以由LINGO等软件直接求得最优解本题我们采用一种基于路径问题的遗传算法，通过在MATLAB中编程求得了较优解遗传算法Genetic Algorithm,简称为GA是基于“适者生存”的一种高度并行、随机和自适应化的优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，最终收敛到“最适应环境”的个体，从而寻求得到问题的最优解或满意解求解本题具体算法流程如下3计算结果针对题目中所给数据用MATLAB软件对该模型进行编程求解得到最短送货总距离为528km由解得到每个送货区的划分，并根据题中所给数据信息可得其区内一组最短路线以及送货一趟所需总时间给每个区送货的总时间送货区序号每个送货区包含的送货点及其一组最短路线115-25—24—

143.07223-18—17—

204.35322-1—

22.834637—13—

192.8353-12—

42.1861-5—16—

22.1867710-29—30—

284.5188-27—

263.54由上图得所有送货总时间约为

25.4967小时，题中要求每个业务员每天平均工作时间不超过6小时由5*6=30〉

25.4967,所以只需5个业务员便可达到要求，如果出现某些送货任务超过6小时而有些不到6小时的时候，只需5个业务员进行轮流换班送货即可据此用MATLAB软件编程对8个送货区进行分组，分为5个组，使每个组的送货总时间为接近6的最优解组号每个组所含送货区送货时间（小时）

74.51

①

24.26

②

585.72

③

135.9

④

465.016

⑤据此需要的业务员数量为5个，无需轮流换班，如果考虑每个业务员之间的公平性则可让每个业务员按天轮流给每个组送货，总的运送公里为528km问题二为公司设计一个费用最省的策略

4.

2.1模型的分析建立在这一问中由于业务员送货行程及其邮件重量决定了主要的费用，与邮递员的安排无关，所以我们以运费总费用最小为目标函数建立模型N km-1min

3.S%RJn i+S,GRjm*2d°Rj+式中（火加）表示第个送货区的第个送货点的邮件重量G jm约束条件每天每个送货点只由一个邮递员送一次货N1=123…307=17每个送货区的送货点个数等于相应的值:k

30.C刍y w--=k；j=

123...30,JJ每个邮递员每次出发带邮件不超过25千克:30E W..G.25j=l

23...30每趟送货不能超过6小时k-\4R.7___y

1.w..+、〃J_______Jk630占6lJ

204.

2.1模型的求解针对题目中所给数据用MATLAB软件采用问题一所述的遗传算法对该模型进行编程求解得到最小费用为15742元由解得到每个送货区的划分，并根据题中所给数据信息可得其区内一组最短路线以及送货一趟所需总时间送货区序号每个送货区包含的送货点及其所需费用（元）一组最短路线114-25—24—

152.7014e+003220-17—18—

232.7156e+00332-9—11—

221.6413e+00346-7—13—

191.4631e+00353-4—

121.0078e+00361―2—5—161122710-29—30—

283.1186e+00388-27—

261.9724e+003问题三在平均每天工作时间允许延长为8小时后建立送货策略此间要求我们如果可以延长业务员的工作时间到8小时,求公司的送货策略这里我们可以沿用问题一的模型，并将其中每趟送货不超过6个小时的约束条件改为不超过8个小时，再用MATLAB软件求得最优送货区的划分送货区序号给每个区送货的总时间每个送货区包含的送货点及其一组最短路线115-25—24—

143.07223-18—17—

204.35322—11—9-

22.836-7—13—

192.83453-12—

42.186135316—

22.1867710329—30—

284.5188-27—

263.54再在工作时间变为8小时的基础上，为每位邮递员分配送货区域，以此来得到一个较优的合理的送货方案由上表得所有送货总时间与问题一的结果一样约为

25.4967小时，题中要求每个业务员每天平均工作时间不超过8时由4*8二32〉

25.4967,得只需4个业务员即可，如果出现某些送货任务超过8小时而有些不到8小时的时候，只需4个业务员进行轮流换班送货即可达到要求据此用MATLAB软件编程对8个送货区进行分组，分为4个组，使每个组的送货总时间为接近8的最优解组号每个组所含送货区送货时间（小时）127

①

345.66

②

585.72

③

676.6967

④据此需要的业务员数量为4个，业务员无需换班，如要考虑每个业务员之间的公平性的话，亦可轮流换班送货总的运送公里为528km

五、模型评价与推广

5.1模型的优点在建立模时我们都是将问题转换为一个数学目标函数，模型结果一方面具体分配出了送货策略，另一方面模型简单清晰，便于理解和推广在求解分析中灵活的将有序路径问题引入到矩阵中，以求解变量路径矩阵的方式进行分区路线的求解；另外在求解过程中用MATLAB并结合运用遗传算法得出了比较理想的送货策略

5.2模型的缺点由于实际中送货问题与许多变量有关，而我们模型中为了使其简化只考虑了少量主要变量，像业务员来回送货时要用时间，还有可能实践中遇到堵车等耗时现象，这些问题都可能使实际结果偏离具体的送货策略另外我们模型完全依靠软件求解，在多变量的情况下数据计算量很大，因此在计算机条件有限的情况下求得最优解比较困难

5.3模型的推广此模型不但能应用于送货策略，也可推广到各种物流分配，车辆运输、城市网络布线等方面。