论文(2).doc

符号及其定义符号符号的意义第i个送货点的接货量第i个送货点到第j个送货点的折线距离模型的假设：根据题意、所给的实际问题和表格中的各种数据进行分析，同时排除实际可能发生的各种因素，如：天气，交通堵塞；人为等，我们可作出以下几点假设：1、表中所给的数据合理与实际情况相符；2、每个业务员都遵守公司的时间规定在时间内完成任务；3、每个业务员在送快递时的速度为题中给定的途中速度25km/h的速度，中途不会发生任何的变速情况；4、保证没一份快递都能安全完整的送到户主手中，确保没有任何意外；5、在题中所给的时间内，业务员送完所有的快递是必须返回公司。6、假设快递公司有多个分公司。模型的建立：由题意和建立的假设来看，若快递公司有若干个分公司的话，我们就可以用分区的方法来将每个坐标区域的运送范围进行分区，按实际生活中的例子每个快递公司常把相对集中的一些点划分到一片区域，业务员负责各自固定的区域。这样就可以达到良好的效率派送快递更加便捷，能够满足客户的需求。另外合理的分区可使运行路线达到最短，同样是节省时间和成本的体现。而且也能更清楚的知道每个业务员的运行线路，以及总的运行公里数。配送分区原则：行车的线路可以根据先分区，再求行车路线。即先根据各种约束条件（如：天气、交通等）进行配送区域的划分，然后各小区域内设计最优行车路线。因此，城市物流配送问题就简化为有装载限制的区域划分和区域内运行路线两个子问题。划分区域的方法：四叉树：四叉树(qua&me)的思想由Klinger在1971年提出。很快在图象处理、空间数据结构描述等方面得到了广泛的应用。四叉树可以将地理空间进行不断的四等分，形成的网格，较好地描述了地理目标的空间位置和空间关系，具有良好的数据结构和地理目标快速检索等特点。在本模型中，运用四叉树的思想进行分区。选取地理上相对集中的送货点构造候选区位，候选区位内各送货点对快递的需求量总和等于或接近业务员最大的运送能力；对候选区位进行优化。确定结果进行分区。问题一：物流分区模型的建立：运用四叉树的思想建立模型时，需要不断的对模型进行四等分法的划分，使得划分的区域满足业务员每次收发的重量不超过公司规定的重量。具体的模型建立如下：1、建立直角坐标系：建立以总公司为原点坐标（0,0）的平面直角坐标系，送货点采用相对坐标方式进行记录，=(，)。2、四叉树网络的生成：以x轴，y轴的最大值的绝对值作为四叉树的最大网格边长。=max( | ，| ，|） =max(|，|，|)。每个网络分别满足货物总需求量小于等于业务员最大承重量为基准进行四叉树的生成，当四叉树网格包含的需求点货物总需求量小于等于业务员最大承重量时，停止该四叉树网格的划分。则该四叉树网格为一个候选配送分区。为了方便描述，把送货点简化为坐标图上的点，用坐标表示位置，总部为原点。过28和30两点做平行X轴Y轴的直线，作四叉树最大网格的边。3、候选区的确定：每个四叉树网络必须满足货物总需求量小于等于业务员最大承重量,先将四叉树的最大网络边长确定下来，然后依次从原点以及x轴和y轴的边缘来划分网络。从原点出发围绕着坐标边缘开始划分网络。过28和30两点做平行X轴Y轴的直线，作四叉树最大网格的边。将图四等分。不能满足网格包括的送货点货物总需求量小于等于业务员运送的最大重量。继续等分网格。当图64等分时满足条件。由于最远端网格邻近又方向小于三的网格，所以选择与该点邻近并方向小于3的网格。沿逆时针方向以邻近原则选择网格进行扩充直至满足供货点货物需求小于等于25，以此方法进行下一个分区，直到分区完毕。4、选定好了候选区后在各个网络里面进行计算需要多少业务员，每个业务员的运行线路，以及总的运行公里数来进行优化。根据计算得出个分区最佳送货线路和所耗时间，如下表：各分区路线此分区送货时间1区0-1-4-6-2-01.71h2区0-3-8-12-9-02.47h3区0-10-22-21-11-02.82h4区0-23-60-28-29-04.59h5区0-15-27-25-03.3h6区0-17-24-26-03.62h7区0-12-19-18-03.06h8区0-5-16-20-14-7-02.99h总路程484km人员安排：一人负责1区5区 一人负责2区7区 一人负责3区8区 4区6区由于往返时间长，分别由一个人负责共5人完成投递任务总计484km路程行动路线如图问题二：费用最省的策略模型建立：由上题可得，我们由四叉树模型得出了合理的送货方案，当我们以最短路线进行送货时可以计算出各条线路的费用，例如 0-1-4-6-2-0 这条线路的费用=其他路线也可以用这种算法来求出费用，再将全部区域的费用相加可得模型的总费用。组数1区2区3区4区5区6区7区8区费用949.51169.11661.83241.92748.42496.81863.21989.2总费用16119.9问题三：时间延长问题的解决时间由六小时延长至八小时后，公司通过安排可以由原五人完成的任务由四人完成，具体到每个人的安排如下表。送货路线送货用时（小时）人员安排每人工作时间（小时）1区0-1-4-6-2-01.71负责1区和4区6.34区0-23-30-28-29-04.592区0-3-8-12-9-02.26负责2区和6区5.886区0