关于送货路线设计问题的分析.docx

送货路线线设计问问题分析析摘要本文是关关于送货货员需要要以最快快的速度度及时送送达货物物的问题题，可看看作是类类货担问题 第一一问中，，我们采采用最近近点插入入模型，，得到了了30个个货物的的送货方方案及路路线时间间，并且且应用局局部全排排列穷举举法将上上面得到到的路线线进行优优化，得得到最终终路线为为：O-->188->113->>19-->244->331->>27-->277->339->>27-->311->331->>34-->400->445->>45-->455->442->499->442->>43-->433->338->>36-->388->335->>32-->322->332->>23-->233->116->>14-->177->221->>26-->O，，总用时时为（包包括交货货时间））：2228.118分 第二二问中，，根据时时间优先先的原则则，将所所有货物物送达点点进行分分块分组组，即优优先送达达时间要要求紧的的货物，，并且利利用穷举举法列举举出每一一块中货货物送达达点的任任意排列列顺序，，求出其其中耗时时最短的的路线即即为所需需结果，，最终路路线为：：O->>18-->133->119->>24-->311->227->>27-->399->227->>31-->311->334->>40-->455->445->>45-->422->499->442->>43-->433->338->>36-->388->335->>32-->322->332->>23-->233->116->>14-->177->221->>26-->O，，总用时时为（包包括交货货时间））：2228.118分。

第三问中中，由于于货物重重量和体体积的限限制，送送货员需需中途取取货我我们采用用最远点点优先送送货和最最近点优优先送货货两种方方案进行行路线的的分划，，并根据据最终求求得结果果的比较较，得出出前者方方案更优优，因此此选用第第一种方方案送货货最终终路线为为：第一趟：：0->>18-->133->111->>12-->155->225->>29-->222->220->>22-->300->228->>33-->288->330->222->115->>5->>2->>4->>3->>8->>1->>6->>1->>7->>10-->9-->144->118->>0,第二趟：：0->>26-->311->119->>24-->311->334->>40-->477->440->>37-->411->446->>48-->444->550->455->336->>27-->399->227->>31-->266->00第三趟：：0->>21-->177->223->>16-->233->332->>35-->388->443->>42-->499->442->>43-->388->366->221->>0第四趟：：0->>26-->266->226->>0总时间为为：3994.33分。

           关键字：：快递公公司送货货 货货郎担问问题 最近近邻点插插入 全排列列穷举法法 1 问题题重述在物流行行业中，，送货员员需要以以最快的的速度及及时将货货物送达达，而且且他们往往往一人人送多个个地方现有一快快递公司司，一送送货员要要按图11中的路路径需将将货物送送至城市市内多处处，要求求设计送送货方案案，使所所用时间间最少假定送送货员只只能沿图图中那些些连通线线路行走走，而不不能走其其它任何何路线各件货货物的相相关信息息见表11，500个位置置点的坐坐标见表表2假定送货货员最大大载重550公斤斤，所带带货物最最大体积积1立方方米送送货员的的平均速速度为224公里里/小时时每件件货物交交接花费费3分钟钟，并假假定，同同一地点点有多件件货物按按照每件件3分钟钟交接计计算现在送货货员要将将1000件货物物送到550个地地点请请完成以以下问题题1. 若若将1~~30号号货物送送到指定定地点并并返回设计最最快完成成路线与与方式给出结结果要要求标出出送货线线路2. 假假定该送送货员从从早上88点上班班开始送送货，要要将1~~30号号货物的的送达时时间不能能超过指指定时间间，请设设计最快快完成路路线与方方式。

要要求标出出送货线线路3. 若若不需要要考虑所所有货物物送达时时间限制制(包括括前300件货物物)，现现在要将将1000件货物物全部送送到指定定地点并并返回设计最最快完成成路线与与方式要求标标出送货货线路，，给出送送完所有有快件的的时间由于受受重量和和体积限限制，送送货员可可中途返返回取货货不考考虑中午午休息时时间  2 问题题分析对于送货货员从快快递公司司库房OO点出发发将货物物送到城城市内制制定地点点问题，，可以转转换为图图论中的的最短路路径求解解问题，，我们将将城市内内的各送送货地点点看做是是图中的的顶点，，各地点点之间送送货所需需的时间间看做是是该边上上的权值值，由题题目表33所给的的各地点点之间的的联通性性构建无无向图对于问题题一，要要求送货货员以最最快的方方式将11~300货物送送达指定定的地点点并返回回因此此，可以以将问题题简化为为货郎担担问题进进行求解解对于问题题二，要要求送货货员从早早上8点点出发，，将货物物在指定定的时间间内以最最快的方方式送达达目的地地，由题题目已知知可以根根据时间间将1~~30号号货物所所对应的的地点分分为4块块，即88：000至9::00、、9:000至99:300、9::30至至10::15、、10::15至至12：：00四四个时间间段。

再再对每个个时间段段内的送送货地点点进行穷穷举，得得到最佳佳路径，，评价各各个时间间段的结结果对于问题题三，在在不考虑虑送货时时间限制制的情况况下，将将体积与与重量两两个因素素考虑在在内，允允许送货货员可以以往返取取货，要要求送货货员以最最快的方方式将货货物送达达指定地地点并返返回由由于所有有物体的的总重量量是1448公斤斤，总体体积为22.988立方米米，送货货员的最最大载货货量为550公斤斤，最大大载货体体积为11立方米米，所以以送货员员会往返返三次取取货，因因此可以以将所有有的送货货地点分分为三块块对于于所有送送货地点点的分块块，可以以采用三三种方案案——寻找找离始发发点最远远的点，，逐次加加入次远远点，直直至达到到送货员员的最大大载货量量；寻找找离始发发点最近近的点，，逐次加加入次近近点，直直至达到到送货员员的最大大载货量量；人为为的分块块，直至至达到送送货员的的最大载载货量；；对此三三种方法法进行评评价，得得出分析析结果 3 模型型假设(1) 送货员员只能走走题目中中给定的的联通路路线，不不能走其其他的任任何路线线；(2) 假定送送货员最最大载重重50公公斤，所所带货物物最大体体积1立立方米；；(3) 假定送送货员的的平均速速度为224公里里/小时时；(4)假假定每件件货物交交接花费费3分钟钟，为简简化起见见，同一一地点有有多件货货物也简简单按照照每件33分钟交交接计算算； (5) 送货员员在送货货期间无无塞车现现象，即即业务员员送快递递途中不不受任何何外界因因素影响响；(6) 送货员员送货期期间不考考虑中午午休息时时间；(7) 假设送送货员到到达送货货点后就就将此站站点上的的所有货货物交付付；  4 模型型的建立立与求解解4.1 各站点点路径求求解模型型在计算机机中通过过编程可可得到坐坐标系中中各站点点的点号号以及11~300号货物物所对应应的站点点号，如如图1——1所示示： 图1—11 所所有送货货站点及及前300各送货货点的标标号 由题目已已知条件件可将送送货问题题看做是是图论求求解最佳佳路径问问题，将将送货站站点看做做是图中中的顶点点，送货货站点之之间的路路径看做做边，将将送货站站点之间间的距离离作为图图中边的的权值，，构成图图，其中中定点数数n=550；因此有算算法求解解图中任任意两站站点直间间的最短短路径，，设图中中权矩阵阵为，其中为到的距离离。

当当；= 其其他算法基本本步骤为为：(1) 输入权权矩阵2) 计算，， ，，其中(3) 中元素素就是到的最短短路长 4.2 问题一一模型的的建立于于求解一、最近近邻点插插入模型型：本题考虑虑应用货货郎担问问题，由由于货郎郎担问题题还没有有一个精精确的算算法，加加之前330个货货物的运运送共涉涉及到222个站站点数据据量较大大，故我我们采用用最邻近近点插入入模型进进行近似似求解其基本本的思想想为：以以O点为为起始点点，纳入入到集合合中，依依次计算算剩余点点到集合合的距离离，取其其中最小小距离所所对应的的站点作作为集合合中下一一个待插插入点，，依次计计算此点点插入到到集合各各元素间间时所对对应的距距离，将将其中最最小距离离所对应应的位置置作为此此点在集集合中的的插入位位置依依次类推推，直到到所有站站点遍历历结束最邻近插插入法实实现步骤骤为：（（设是带带权无向向图，共共有n个个结点，，其中nn=222）(1) 以O点点为初始始点计作作，建立立有序集集合（集集合元素素排列顺顺序即为为最佳路路径）=={}，，并由其其余的nn-1个个点建立立集合=={}，，计算集集合中每每一个元元素到集集合中各各个元素素的距离离，取集集合中每每一个元元素到集集合中每每一个元元素的最最小距离离作为其其对应与与集合的的距离，，比较集集合中各各个元素素到集合合的距离离，取距距离最小小所对应应的元素素作为集集合的待待纳入元元素，将将其分别别插入到到集合各各个元素素之间，，计算其其距离，， 取最最短距离离所对应应的插入入点作为为该元素素在集合合中的最最终位置置，得到到最终的的有序集集合。

2）假假设集合合={}，，={}，，求出集集合中元元素分别别到集合合中元素素之间的的距离，，依次即即为，比比较的大大小，取取其中最最小的值值作为到到集合的的距离；；再求集集合中元元素分别别到集合合中元素素之间的的距离，，依次即即为，比比较的大大小，取取其中最最小的值值作为到到集合的的距离；；依次类类推，求求出集合合中各元元素到集集合的距距离比比较集合合的各个个元素到到集合距距离的大大小，取取其中距距离最小小的元素素为待插插入集合合的元素素，为了了便于理理解这里里我们假假设此元元素为，，然后计计算插入入到集合合元素，，以及后所所得路径径的总距距离，取取其中距距离最小小的一组组作为的的插入点点，得到到集合 (3)) 依次次类推，，直到所所有的点点遍历一一遍，得得到的集集合即为为最佳路路径由程序可可得其最最佳路径径为：O->221->>17-->144->116->>23-->322->335->>38-->366->338->>43-->422->449->>42-->455->440->344->331->>18-->133->119->>24-->311->227->>39-->277->331->>26-->0总的时间间为：2230..83分分。

二、局部部全排列列穷举法法模型前30个个货物的的运送共共涉及到到22个个站点数数据量较较大，直直接采用用全排列列穷举法法难以实实现，因因此我问问现将其其分块，，并在每每块内部部采用局局部全排排列穷举举法得到到局部最最佳路径径，在通通过固定定每一块块路径的的起始点点的方法法是所有有块的路路径连接接成一个个整体具体体模型算算法见下下文问题题二）。