程序代写代做代考 宁愿使用稍微低级但有效的程序,不能是高级但是无法运行/有错误的程序
宁愿使用稍微低级但有效的程序,不能是高级但是无法运行/有错误的程序
概括
1. 写程序,用“随机优化技术”(stochastic optimization technique)解决车辆路径问题
2. 用 descent-based method/random descent method和其他复杂方法解决问题。
3. 程序运行过程中和最后要有适当的图表输出
每天一家运输公司都会给出一份交货地点的列表。运输公司有一队车辆,早上从仓库出发。每一个独立的车辆离开仓库以后访问(到达)一些给定了顺序的位置。公司希望最小化车辆行驶的总距离,并且确保到达了所有的交货地点。
路径问题具体说明如下:给定一个指定仓库位置的单个坐标和n个交货地点坐标。规定可用车辆数量为v ∈[1,n ]
公司规定:所有司机必须每天到达m个交货地点,m=n/v(假设n/v永远是整数)。任何两个位置(包括仓库)之间的距离假定都为直线(就像TSP例子中那样)
实例问题在文本文件中
文本文件从仓库坐标开始,然后是数字n 和v, 其后是n个交付中的每一个坐标
这里的例子中n=9, v=3(因此m=3),仓库如第一行所给出的在坐标(3.3)处。所有的坐标都是整数)
这个问题的候选解决方案可以方便地存储为具有v行和m列的2D数组。这里,分配给车辆i的位置以给定的顺序出现在i行(rows)中。例如,以下数组S指的是下面所示的解(使用上面给出的问题)。
成本(cost)是所有v个车辆行驶的距离的总和。我们的任务是找到一个最小化这种成本的解决方案。此成本计算:
其中函数 D() 表示两个位置的坐标之间的直线距离。
例如,在S方案中,车辆1要访问以下位置:(Depot,4,1,5,Depot)。因此,它的访问坐标是(3,3),(2,5),(2,7),(3,4),(3,3)。
所以车辆1的总距离(2.24+2+3.16+1)= 8.4。同理,车辆2有10.9的距离,车辆3具有16.29的距离。
问题1
已经给出三个问题文件:p1.txt,p2.txt和p3.txt,每个都有上述布局。我们的第一个任务是编写一个程序,读取所有上述信息。接下来,你的程序应该以随机的方式(一开始不需要复杂的启发式方法 – 随机赋值就行了)产生这个问题的初始解决方案。然后写出成本函数cost,计算此解决方案的成本。
Tips:
成本函数正确与否至关重要。因此,有必要使用非常小的问题文件p1.txt来手动检查结果。不要忘记为每个车辆计算包括到达车库的距离
问题2
改进初始解决方案的代码。使用随机下降技术(random descent technique)来实现。为此,需要设计一个合适的邻域运算符(neighborhood (move) operator)。使用随即下降技术改善后的成本应小于等于初始成本,并且运行一定数量的迭代。
问题3
修改代码和工作表,输出以下信息:(a)迭代图Vs成本折线图(line-graph),显示成本如何在迭代运行中降低;(b)在运行期间找到的最佳路线的图表展示(如上述s方案示例)。图标展示最好是动态的,即它们在运行期间(随着解决方案被改进)改变。请注意,在每次迭代中更新图表可能会使算法变慢,因此可能每100次迭代更新一次图表比较合适。
问题4 (三选2即可,选最简单的就行,但是要保证回答正确,有效)
完成问题1-3以后
1.优化代码:例如运行时,可能S(车辆)中只有部分行(rows)被更改。尝试通过重新评估受影响的行来加速程序。
2. 在初始解决方案中,采用了随机赋值,有没有更好的赋值方法呢?
3. 使用更有效的搜索技术:不用简单的随机下降技术,而采用例如退火算法,洪水算法,相邻运算符(neighborhood operators)等等。
问题5
1. 将代码分解成小的,有意义的子过程和函数;
2. 使用适当的类型声明所有变量(强制变量声明);
3. 适当注释和缩进代码;
4. 创建一个可呈现的,用户友好的界面。
在每次运行结束时,最终解决方案(从运行中观察到的最佳解决方案)应放入电子表格中:将成本放入单元格A1中,然后将整个解决方案打印在下面的单元格中。请注意,老师将使用他自己的检查程序来确认这些解决方案的成本与您声明的成本相同,因此格式很重要。格式如下:
/docProps/thumbnail.jpeg