利用“图”的知识解决送货最优问题(求助)
假定所有快件在早上7点钟到达,早上9点钟开始派送,要求与当天17点之前必须派送完毕,每个业务员每天平均工作时间不超过6小时,在每个送货点停留的时间为10分钟,途中速度为25km/h,每次出发最多能带25千克的重量。为了计算方便,我们将快件一律用重量来衡量,平均每天收到总重量为184.5千克,公司总部位于坐标原点,每个送货点的位置和快件重量如下表所示,并且假设街道平行于坐标轴方向。请你运用有关数学建模的知识,给该公司提供一个合理的送货策略(需要多少业务员,每个业务员的运行线路,以及总的运行公里数)。
如果业务员负重时的速度是20km/h,获得酬金是3元/km*kg;而不携带快件时的速度是30km/h,酬金是2元/km,请为公司设计一个费用最省的策略。
送货点 快件量T 坐标(km) 送货点 快件量T 坐标(km)
x y x y
1 8 3 2 16 3.5 2 16
2 8.2 1 5 17 5.8 6 18
3 6 5 4 18 7.5 11 17
4 5.5 4 7 19 7.8 15 12
6 3 0 8 15 3.4 19 9
5 4.5 3 11 32 6.2 22 5
7 7.2 7 9 22 6.8 21 0
8 2.3 9 6 23 2.4 27 9
9 1.4 10 2 24 7.6 15 19
10 6.5 14 0 25 9.6 15 14
11 4.1 17 3 26 10 20 17
12 12.7 14 6 27 12 21 13
13 5.8 12 9 28 6.0 24 20
14 3.8 10 12 29 8.1 25 16
20 4.6 7 14 30 4.2 28 18
点的分布如附件所示....
利用“图”的知识,将送货点抽象为“图”中是顶点,由于街道和坐标轴平行,即任意两顶点之间都有路。在此模型中,将两点之间的路线权值赋为这两点横纵坐标之和。如A(x1,y1),B(x2,y2)两点,则权值为Q=|x2-x1|+|y2-y1|。并利用计算机程序对以上结果进行了校核。经典的Dijkstra算法和 Floyd算法思路清楚、 方法简便,但随着配送点数的增加,计算的复杂性以配送点数的平方增加,并具有一定的主观性. 所以本研究在利用动态规划法的基础上引入扑食搜索法的原理,提高辆车的装载率,从而减少车辆的需求,达到降低成本的目的.
求高手指点代码如何编写......