送货路线设计问题分析(西工大优秀论文)

《送货路线设计问题分析(西工大优秀论文)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、送货路线设计问题分析摘要本文是关于送货员需要以最快的速度及时送达货物的问题，可看作是类货郎担问题。第一问中，我们采用最近点插入模型，得到了30个货物的送货方案及路线时间，并且应用局部全排列穷举法将上面得到的路线进行优化，得到最终路线为：O->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45->45->42->49->42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->O，

2、总用时为（包括交货时间）：228.18分。第二问中，根据时间优先的原则，将所有货物送达点进行分块分组，即优先送达时间要求紧的货物，并且利用穷举法列举出每一块中货物送达点的任意排列顺序，求出其中耗时最短的路线即为所需结果，最终路线为：O->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45->45->42->49->42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->O，总用

3、时为（包括交货时间）：228.18分。第三问中，由于货物重量和体积的限制，送货员需中途取货。我们采用最远点优先送货和最近点优先送货两种方案进行路线的分划，并根据最终求得结果的比较，得出前者方案更优，因此选用第一种方案送货。最终路线为：第一趟：0->18->13->11->12->15->25->29->22->20->22->30->28->33->28->30->22->15->5->2->4->3->8->1->6->1->7->10->9->14->18->0,第二趟：0->26->31->19->24->31->

4、34->40->47->40->37->41->46->48->44->50->45->36->27->39->27->31->26->0第三趟：0->21->17->23->16->23->32->35->38->43->42->49->42->43->38->36->21->0第四趟：0->26->26->26->0总时间为：394.3分。关键字：快递公司送货货郎担问题最近邻点插入全排列穷举法1问题重述在物流行业中，送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方。现有一快递公司，一送货员要按图1中的

5、路径需将货物送至城市内多处，要求设计送货方案，使所用时间最少。假定送货员只能沿图中那些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。每件货物交接花费3分钟，并假定，同一地点有多件货物按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1.若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2.假定该送货员从早上8点上班开始送货

6、，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3.若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。不考虑中午休息时间。2问题分析对于送货员从快递公司库房O点出发将货物送到城市内制定地点问题，可以转换为图论中的最短路径求解问题，我们将城市内的各送货地点看做是图中的顶点，各地点之间送货所需的时间看做是该边上的权值，由题目表

7、3所给的各地点之间的联通性构建无向图。对于问题一，要求送货员以最快的方式将1~30货物送达指定的地点并返回。因此，可以将问题简化为货郎担问题进行求解。对于问题二，要求送货员从早上8点出发，将货物在指定的时间内以最快的方式送达目的地，由题目已知可以根据时间将1~30号货物所对应的地点分为4块，即8：00至9:00、9:00至9:30、9:30至10:15、10:15至12：00四个时间段。再对每个时间段内的送货地点进行穷举，得到最佳路径，评价各个时间段的结果。对于问题三，在不考虑送货时间限制的情况下，将体积与重量两个因素考

8、虑在内，允许送货员可以往返取货，要求送货员以最快的方式将货物送达指定地点并返回。由于所有物体的总重量是148公斤，总体积为2.98立方米，送货员的最大载货量为50公斤，最大载货体积为1立方米，所以送货员会往返三次取货，因此可以将所有的送货地点分为三块。对于所有送货地点的分块，可以采用三种方案——寻找离始发点最远的点，