| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 555 人关注过本帖
标题:利用“图”的知识解决送货最优问题(求助)
只看楼主 加入收藏
satanjerk
Rank: 1
等 级:新手上路
帖 子:10
专家分:4
注 册:2009-5-30
结帖率:50%
收藏
 问题点数:0 回复次数:0 
利用“图”的知识解决送货最优问题(求助)
假定所有快件在早上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算法思路清楚、 方法简便,但随着配送点数的增加,计算的复杂性以配送点数的平方增加,并具有一定的主观性. 所以本研究在利用动态规划法的基础上引入扑食搜索法的原理,提高辆车的装载率,从而减少车辆的需求,达到降低成本的目的.


求高手指点代码如何编写......

图片1.jpg (12.49 KB)
图片附件: 游客没有浏览图片的权限,请 登录注册
搜索更多相关主题的帖子: 知识 送货 
2009-08-18 15:40
快速回复:利用“图”的知识解决送货最优问题(求助)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017307 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved