改进的启发式搜索算法求解农机调度问题

《改进的启发式搜索算法求解农机调度问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、改进的启发式搜索算法求解农机调度问题摘要：针对农村土地流转形成的大规模土地，提出基于轮盘的启发式搜索(Heuristicsearchbasedonroulette,HSBOR)算法和基于最小值的启发式搜索(Heuristicsearchbasedonminimum,HSBOM)算法，求解跨区域农机调度问题；构建农机调度模型，设计HSBOR和HSBOM算法的核心思想，并通过模拟试验比较HSBOR、HSBOM算法与基于优先级规则的启发式(Heuristicbasedonpriorityrules，HBOPR)算法在调度成本、运行效率上的优劣。结果表明，HSBOM算法在

2、调度成本和运行效率上最优。关键词：跨区作业；启发式搜索算法；农机调度中图分类号：S232.3文献标识码：A文章编号:0439-8114(2016)16-4280-03DOI：10.14088/j.cnki.issn0439-8114.2016.16.053中国是传统的农业社会，在工业化、现代化转型过程中产生了土地流转问题，土地流转使农业经营模式规模化、集约化、现代化。大规模土地生产，农机跨区域作业问题有待解决。农机调度问题是车辆路径问题(Vehicleroutingproblem，VRP)[1-3]的进化，VRP问题中构造的问题模型是一对多的，即在一定范围内，一个

3、出发点对应多个终点的问题。而农机调度问题是多对多的NP-hard问题［4-7］，即农机场个数与农田作业点个数均为多个，农机场有效为农田分配农机的问题。针对多对多的农机调度问题，本研究提出了HSBOR和HSBOM算法，并与基于优先规则的启发式农机调度算法进行比较，3种算法都是在农机充足的情况下为农田分配农机，HBOPR算法制定了农田得到农机的优先级，而在实际应用当中，农田的重要程度是相近的。由此，HSBOR算法引入了农田地位平等的思想，按照轮循的方式平等地为农田分配农机，保证每个农田都能得到距离自己较近的农机。HSBOM算法根据距离的远近为农田分配农机，将所有距离数

4、据存入数据库，与农田距离最小的农机优先分配，分配完成一次，数据库更新，直到所有农田得到所需的农机数量。结果表明，HSBOR和HSBOM算法比HBOPR算法调度成本均有所降低，而运行效率上，HSBOR算法比HBOPR算法稍低，HSBOM算法与HBOPR算法效率相近，两种算法具有可行性。1问题描述本研宄的农机调度问题可描述为：在一定区域内，存在两个农机点，3个农田作业点。两个农机点的农机可以为3个农田按需分配，农机点与农田作业点的连线表示两点之间的路径，路径上的标识表示两点之间的距离。如图1所示，（V，D），V表示图1中的顶点，有两种类型，长方形Mi表示第i个农机点，

5、k表示农机点的个数，其中l

6、大，状态搜索算法将会出现严重偏差，且算法效率低。本研究对改进的HSBOR算法核心思想和HSBOM算法的关键步骤进行详细阐述。2.1HSBOR算法核心思想将农田按照开始工作时间从早到晚排序，为今后研究在农机不充足的情况下，农机在农田之间进行二次分配作铺垫。排序好的农田依次放在同一个轮盘中。Fn,在轮盘假设排序好的农田为Fl，F2,F3,中显示效果如图2所示。扇形的大小代表农田面积，扇形面积越大，表示农田面积越大。分配过程可描述为：从图中“开始位置”处依次为每个农田分配农机，每次只为农田分配一台农机，完成一次分配后，轮盘按照图中箭头所示，顺时针旋转一个扇形，直到为所有

7、农田分配完所需农机数量，分配过程结束。2.2HSBOM算法关键步骤HSBOM算法核心思想是根据农机点到农田作业点的距离，为农田分配农机，距离农田作业点小的农机优先分配，保证分配的农机距离农田作业点尽可能小，减少调度过程中的调度成本，HSBOM算法的具体流程如下：Step1:初始化二维数组result[][]，存储分配结果，整数变量i=0，控制循环语句；Step2：将农机点到农田作业点距离按照从小到大的顺序排序，存储在sort[]中，保留农机编号与农场编号的对应关系；Step3:得到sort[]中最小距离所在农田位置indexF；Step4:ifiO,农田至少所需车

8、辆〉0,转