兰州交通大学2009年数学建模竞赛B题论文.doc

兰州交通大学2009年大学生数学建摸竞赛论文题目： 快递公司送货策略（B题）参赛人1： 姓名 赵 杰学院 数理与软件工程学院班级 软件工程071班参赛人2： 姓名 张书呈学院 数理与软件工程学院班级 软件工程071班参赛人3： 姓名 国艳松学院 数理与软件工程学院班级 软件工程071班学校统一编号，个人不得填写论文编号： 快递公司送货策略(B题)摘 要本文是关于快递公司在已经收到确定数量的快件的情况下，在需要派送费用最省的情况下，如何确定多少业务员去派送这些快件的问题。本文建立了一个从两个方面去解决这个问题的模型，第一: 利用四叉树栅格索引的方法将客户所在地划分成若干个满足派送快件时间最省的分区；第二:在每一个小派送区中选择一条最佳路径，使得走这条路径所花的时间最短。首先我们采用了四叉树栅格索引的方法对所确定的客户区进行分区，每个区满足该区的所有客户的快件重量之和小于或等于25kg。区分好后，再用所求的的目标函数对每一个区进行优化，优化的目的就是要让该区客户的快件重量之和尽量接近25kg并且尽量靠近公司所在地。分区确定好后，必须找出从公司出发到达某一个区并把该区的快件送完再回到公司的最短路径（即巡回路线最短）。这个问题可以转化为经典的旅行商问题（TSP）来解决，解决旅行商问题的算法很多，在此我们采用了经典的遗传算法来确定每一个区的最佳路径，具体的实现是利用计算机编程来解决这个问题，路径确定好后，我们按照行走路径就可以算出送完所有快件的总时间 24.30小时，即24小时18分钟。如果按照每一个业务员的平均工作时间为6个小时来确定工业务员人数的话，在实际情况下4个业务员就应该能够送完所有快件。按照所确定的最短路径进行总路程长度的计算，得到总的行里路程为482 km。快递公司送货策略1 问题的提出 快递公司一般将收到的快件集中放到总部，然后由业务员进行派送，派送地点已经明确。每个业务员工作的平均时间不超过6小时，并且一个业务员每次出发所携带快件的重量不能超过25kg。公司为了节约成本，必须要用最少的人在规定的时间内把所有的快递送到客户家中，因此选择什么样的派送路线和派遣多少业务员得尤为重要。本论文试图从最优化的角度，建立起满足快递公司选择恰当数量业务员的数学模型，借助计算机的高速运算能力和逻辑判断能力，求出公司派遣的业务员数量和业务员的送货路线。2 问题的分析为了分析问题方便，首先建立坐标系。以快递公司的总部作为原点O，过原点的水平线OX作为X轴的正方向，过原点垂直于X轴指向正前方的水平线OY作为Y轴建立高斯平面直角坐标系。每个客户所在地用一个点表示（如图1），( 图1)点的横纵坐标之和表示公司和客户所在地之间的距离。现在在客户的坐标值中求出距离原点O的最远的横纵坐标值Xk和Yk。以Xk和Yk作为边长，以原点作为矩形的第一个对角点在XY轴正方向所确定的区域画出一个长为20km宽为28km的矩形，采用四叉树对该地区进行四等分，形成2m2m的网格 。具体是这样的：把这个矩形首先分成4个区，所有的客户都被分到某一个区内。检查每一个区所要送的快件的重量之和是否达到25kg，如果有一个区的总重量超过25kg，则继续在每一个小区再进行分区，直到所有区的总重量都不超过25kg为止。分完之后，确定了16个区，(如图2) 在这里m=2。在这16个区中，(图2)有些区的送货重量是远远达不到25kg的，因此必须对每一个区进行拆分和组合。也就是确定候选区，选择距离公司送货点最远的四叉树网格，沿逆时针方向进行网格中需求点的扩充，扩充的条件是：如果本网格中的快件总数量小于25kg，则进行扩充，否则不扩充。重复操作这一步，直到每一个送货点都被分到某一个区里面，通过改进方法，对配送分区进行优化，优化的方法必须满足一定的条件。区位确定好后，再来确定对该区进行送货路线，送货路线的确定必须满足业务员花的时间最少，也就是走的路程最短。这就是运输巡回路线问题的求解，我们采用的是典型的旅行商问题求解法来求解，通过计算机的高速运算能力和逻辑判断能力来确定所走到路线。根据送货路线求出每一个区送货的时间，根据时间的长短来安排业务员的数量以及每个业务员所要走的区。这样就可以求出该快递公司所需要的业务员的数量和成本。3模型假设每次业务员从一个区送货回来，再配货的时间为0，即不花时间。业务员不会发生意外，即不会意外的花一些时间。业务员中途不休息。与业务员走的路都为横纵坐标。街道平行于坐标轴。业务员在中途除了送货之外没有别的时间耽搁。4符号说明 ai ：第i分区，距离公司最近的客户点。其值为1，否则问0 。bij ：客户j属于第i分区。其值为1，否则为0；lij ：客户j到距离公司最近客户点i之间的距离。wj ：客户j的快件重量。di ：第i分取中距离公司最近的客户点到公司的距离 z ：每一个业务员所能承载的最大快件量。xij ：=1（弧（i，j）在线路上），或0（弧（i，j）不在线路上）。dij : 任意两个客户之间的距离dij=|xi-xj|+|yi-yj|。5模型的建立及求解快递公司分区配送货物的数学模型主要分为两个相对独立的部分：配送分区模型和运行线路模型。在运行线路模型中将每一个区都使用一次运行线路的计算，则构造出了相应的几条合适的路线。配送分区的数学模型如下所示： mincost=inaidi+injnbijlij (5-1) in-1bij=1 (5-2) in-1bijwjz (5-3) bijai (5-4) ai = 1，0 (55) bi j = 1，0 (56)式（11）为目标函数，使得走过的路径最短；式（12）表示每一个客户点都被选中；式（13） 表示每一分区的总快件的重量的限制，均小于每一个业务员的负重量。式（14）表示分区i和客户j之间的关系。式（15）和（16）限制 ai和bij 的取值范围。运行线路模型： 运行线路模型采用经典的旅行商问题的数学模型来求解 如下：mincost=injndijxij (5-7) i=0nxij=1 j=0,1,n (5-8) j=0nxij=1,i=0,1,n (5-9) xij=0,1 (5-10)51 配送分区的划分(1) 高斯平面直角坐标系的建立。建立以公司为原点(0,0)的高斯平面直角坐标系，需求点采用相对坐标的方式进行记录，vk=(xk, yk,) (1k30)。(2) 四叉树的生成 。 检索需求点中xk 和yk最大的绝对值作为建立四叉树的最大网格边长 Lx = max(|x1|，|x2|，|x3|，|x4|，|x5| , |x30|)，Ly= max(|y1|，|y2|，|y3|，|y4|，|y5| , |y30|)。以四叉树中网格包含的客户点快件总重量小于或等于业务员一次能够带走的最大的快件重量(25kg)为基准进行四叉树的生成，当四叉树网格包含的客户的快件总重量小于或等于每个业务员所能够带走的重量时，停止该四叉树网格的划分，则该四叉树网格中的每一格就为就为一个候选配送区。剔除不包含客户点的四叉树网格(3) 确定后选分区，选择距离公司最远的四叉树网格，沿逆时针方向进行网格中客户点的扩充。如果与之临近网格中由方向度小于3的网格，则以临近网格中最小方向度的网格为中心进行扩充，原网格作为次选网格。扩充的条件是：如果本网格的总需求量等于每个业务员一次所带的重量(25kg)则不进行扩充，如果本网格的需求量不到25kg则沿逆时针方向以最近原则选择相邻一定等级的网格内的客户点，使配送区位的快件总重量等于或接近25kg。所选择的客户点从原来的配送分区中删除，将无需求点的网格删除。(4) 重复操作(3) 直到使每一个客户点仅一次被选择如一个配送区。(5) 将以上操作确定的配送区位任作为候选区，通过改进算法的方式带入分区算法中的目标函数，进行目标函数求解，如果求解值小于目标函数求解值则该配送区位作为新的配送区位，循环上述操作，进过有限次的计算，进行配送区位的优化，优化的结果如图3。(图3)52 运行路线的确定采用旅行商问题的解法。改解法采用计算机辅助计算来解决。程序的伪代码和步骤如下：(1) 选取公司作为线路起点i；(2) 构造点击的凸集和，取得一条初始路线；(3) 选择一条不属于初始路线上的点k以线路上的弧(i ,j)，使由弧(i,k)于弧(k,j)构成的角度最大。(4) 将点k插入到i和j之间。(5) 重复上述步骤知道得到一条哈密尔顿回路为止得到了8个区域图，如图4所示(6) 计算机辅助计算的结果(如图4)。(7) 业务员应该走的路线就是下图所示的路线(其中“入口”表示某个业务员从公司(原点)到该分配区位的第一个点。“出口”表示业务员已经走完该区到达的最后一个客户点 )(图4)53 时间和路程长度的确定 将每一个区都进行运行线路的确定的计算，最后得到了几条合适的运行线路。 (如表1)。表1.业务员载重量25kg,总需求量184.5kg,分为8区区位需求点分区总量(单位kg）巡回路线(原点O为始点和终点)127,29,3024.3O273029O224,26,2823.6O262824O318,19,2524.9O192518O45,6,16,17,2021.4O61617205O54,7,8,13,1424.6O8131474O61,2,322.2O132O79,10,11,2218.8O1022119O812,15,23,3224.7O12152332O 再根据所走的路线来确定总共的行程和总共需要的时间以及每一条路线所需要的时间(如表2) 表2区位每分区总路程单位km每分区路途所时间 单位小时h每分区货点所需时间 单位小时h每分区所需总时间 单位小时h19292/25=3.68310/60=0.54.1828888/25=3.52310/60=0.54.0236464/25=2.56310/60=0.53.0645050/25=2510/600.842.8454848/25=1.92510/600.842.7662020/25=0.8310/60=0.51.374848/25=1.92410/600.672.5987272/25=2.88410/600.673.55总的运行路程482 km总的运行时间24.3 hours 根据时间表，找出可以互补的几条路线，互补的条件就是两条路线所需时间相加之后时间之和在6小时附近。这样确定下来的时间和总共要的人数是24.30hours和4.050个人现在确定每个人要走的路线。假如有4个业务员，他们所走的分区和所花的时间(如表3)：表3业务员的编号所走的分区所花时间 (单位 小时h)1号1区，6区5.482号2区，7区6.613号3区，4区5.904号5区，8区6.316 设计规范的合理性讨论6.1 合理的方面 快递公司每天要运送的快件在早上出发时间之前已经全到了，没有到的当天就不运送，这是许多公司现在的经营模式，这种模型现在已经很成熟，因此采用这种解法应该能够达到公司的节约成本要求。6.2 不和理的方面 由于城市快件的传递是一个比较复杂的问题设计到众多的变量，上述模型尚有许多因素没有考虑在内。比如每一次业务员送完快件，回来再准备第二趟运送快件这个过程也要花时间，这个时间没有考虑到时间范围内。还有像城市交通不平衡等问题，货物分类等问题。7 结果和误差分析理论上总时间算下来是24.30小时，每个业务员平均工作6个小时，因此人数算下来平均是4.050个人，在实际情况中4个人就能送完所有的快件。8 模型推广该模型可用于很多领域，比如说城市物流分配问题，城市网络布线等问题。9 模型的优缺点 该模型实用性很强，从计算机运算结果来看，走过的路径还算是比较优的。但是这里面忽略了很多因素，这些因素在实际中不可忽略。因此实际中应该多分配一些时间或业务员。10 参考文献1 霍亮 空间物