模拟退火算法求解最短路径填挖问题

Solving the Shortest Route Cut and Fill Problem Using Simulated Annealing Algorithms

在大型的工程和建筑项目中,经常要进行场地平整工作。这引出了一个最短路径填挖问题,目标是找到一个最小车辆路径,使得整个施工过程的总运输距离最短。该问题属于NP-hard问题。本文采用模拟退火算法求解该问题。最后通过算例计算,并同贪婪算法的求解结果进行比较,验证了模拟退火算法的高效性。

Heavy engineering and construction projects often require terrain modifications. So the shortest cut and fill problem（SRCFP） is introduced. The objective of SRCFP is to find a vehicle route that minimizes the total distance traveled between cut and fill locations. It＇s a NP-hard problem. Simulated annealing algorithms are formulated to address the SRCFP. A greedy algorithm is constructed to assess the effectiveness of simulated annealing on the SRCFP.