论文部分内容阅读
［摘 要］根据装载地域分配影响因素，建立了装载地域分配的数学模型，并分析了装载地域分配组合优化问题的复杂性，同时设计了遗传算法对问题进行求解。
［关键词］ 军事物流 装载地域分配 遗传算法
装载地域保障是部队在军事物流过程中，以铁路为主要方式进行输送的重要物质和设备基础，是编制保障方案的重要内容之一。选择良好的具有保障部队不同进度条件下实施铁路输送能力的装载地域，对于保障部队安全、快速、正点地实施军事物流具有十分重要的意义。装载地域各装载点的优化分配方案可以有效地缩短部队的整体输送时间。长期以来，各装载站分配方案的制定，通常采用人工试探的方法，这种方法不仅费时费力，且经验型东西太多，具有很大的局限性，很难适应未来战时部队铁路输送的需要。因此，研究部队铁路输送保障中的装载地域分配问题的数学模型和求解算法，并应用于相关铁路军事运输辅助决策系统，是未来非线性战争中提高军交运输指挥效能的客观要求。
本文根据装载地域分配使用影响因素，建立了以对列车梯队分配装载站的总得分值为依据的装载地域分配模型，分析了该问题的复杂性，并设计了遗传算法来进行求解。
一、装载地域分配影响因素分析
铁路军事运输的装载需要在技术设备条件良好，运输组织方法适合的铁路车站上进行。在战役部队铁路输送时，由于部队驻地和到达装载地域的不同，为保证输送进度和序列实施，就需要选择多个铁路车站承担部队输送的装载作业，这些车站就构成了部队的装载地域。影响装载地域中装载站分配的因素很多，其中最主要的有以下几个：
1.装卸载能力。装卸载地域的装卸载能力是由该地域内各装卸载站的装卸载能力决定的。它的定义是：在一定的固定和活动设备以及装卸载和行车组织方法的条件下，一个装卸载地域在单位时间内（通常为一昼夜）所能装卸载的最大列车数。装卸载地域能力的大小，直接影响被运部队的输送进度和输送序列。
2.部队驻地与各装载站的距离。部队驻地距离装载站越远，部队的机动距离就越长，耗费也就越大。所以，应尽量选择离部队驻地近的装载站，这样可以减少部队的摩托化或徒步行进的距离，便于部队组织管理和进行各种保障。
3.部队输送进度。输送进度是指部队每昼夜按平均间隔发出的列车数。输送进度必须与装载地域的装载能力相匹配。
4.部队输送序列。输送序列是指各被运部队的开进顺序。
二、装载地域分配模型的建立
装载地域分配问题的描述为：在某个装载地域有n个装载站，待输送部队共有k个梯队，输送期限为m天，输送进度为P，问如何对各梯队分配装载站，使得满足输送序列和输送进度要求。
定义如下变量：
si表示第i个装载站；tj表示第j个梯队；表示车站i在第l天输送的列车梯队数，列；表示车站i的装载能力，列；表示第j个梯队离开装载地域的时间；P表示部队输送进度；表示梯队j选择车站i的得分值；
式(1)是目标函数，表示对列车梯队分配装载站的总得分值最大的那种分配方案；式(2)是装载能力限制，表示各装载站在任意一天内发出的列车数均不超过该装载站的装载能力；式(3)是输送序列限制，表示各列车梯队必须按输送序列发送；式(4)是输送进度限制，表示各装载站每天的装载列数都必须等于输送进度。
显然，所建立的模型是带有复杂约束的混合整数非线性规划模型，属于NP-hard问题。对于这类问题，传统的精确算法存在很多的局限性。比如说穷举法，它的时间复杂度为O(Nn)，N为问题的规模，n为运行次数。当N不断增大时，运行时间将迅速增加，如图所示。如果假设运算每一种分配方案所用时间为1s，那么计算3个装载站，30个梯队的部队输送装载站分配问题所花费的时间为6528765年。由此可看出大规模的部队输送装载站分配问题的复杂性。
三、遗传算法的设计
遗传算法起源于对生物系统所进行的计算机模拟研究。它具有实用、高效、鲁棒性强的特点，利用遗传算法可以得到问题的满意解。
1.设计染色体结构。为了提高效率，采用自然数编码，即序数编码。则装载地域分配的一条可行的染色体结构为（i1, i2,…, it,…, ik），t∈[1, k]且为自然数，it∈[1, n]且为自然数。k为待运部队的梯队数，n为装载地域内的车站数，it表示第t个列车梯队所选定的装载站。
2.确定初始种群。为了保证计算效率，群体规模不能太大，也不能太小，在这里规定群体规模取值为20到50之间。
3.确定适应度函数。适应度函数是由目标函数变换而成的。由于本文的目标是求对列车梯队分配总得分值最大的装载站，所以设计的适应度函数为： Fit(z) = z
4.设计遗传算子。对于选择算子，采用精英策略和随机竞争相结合的方法，在随机竞争选择时，每次按轮盘赌选择机制选取一对个体，然后让这一对个体进行竞争，适应度高的个体被选中，如此反复，直至选满为止。对于交叉算子，可采用两点交叉运算。变异算子采用对换变异。
5.设定终止条件。由于遗传算法具有较大的随机性，本文设计了2个终止条件：一是若迭代次数达到1000代；二是若最佳染色体连续保持10代。当遗传算法运算过程中满足任一个终止条件，就结束运算。
6.遗传算法的步骤
Step1：设置遗传算法的参数，即进化总迭代次数maxgen，种群规模popsize，交叉概率pc，变异概率pm；
Step2：进化迭代次数gen=0，随机产生popsize条染色体生成初始种群；
Step3：计算种群所有个体的适应度函数值；
Step4：选择操作，采用精英策略和轮盘赌的方法从群体中选择染色体作为父代染色体；
Step5：交叉操作，按照交叉概率对选择出的染色体进行交叉操作；
Step6：变异操作，按照变异概率对染色体进行变异操作；
Step7：不断进行遗传操作，直至生成的染色体的个数达到种群规模popsize，组成下一代群体，gen= gen+1；
Step8：如果gen>maxgen，算法结束，否则转Step3。
四、结束语
通过实验，对一个师规模部队，应用遗传算法在求解部队铁路输送装载地域分配问题时，可以在很短的时间内求得一个比较优的解。得到的装载站的分配使用方案是合理的，不仅满足装载地域分配的基本要求，同时也保证了部队的输送进度和输送序列。本文建立了贴合部队铁路输送装载地域分配的数学优化模型，并应用遗传算法对问题进行了求解。部队铁路输送中装载地域分配问题是典型的NP问题，随着问题规模的增加，优化搜索的计算量迅速增长，算法效率必然会下降。因此，在保证算法求解精度的前提下，进一步改进算法，提高算法的效率，是下一步的研究方向。
参考文献:
[1]鲍平鑫,徐开启.铁路军事运输［M］.北京:解放军出版社,2006.
[2]刘中,周飞飞,李海华.军运梯队铁路装载组合优化问题模拟退火算法研究［J］.军事交通学院学报,2010，(2)21-24。
[3]吴晓东.大规模部队铁路输送研究.北京交通大学博士论文,2008
[4]邢文训,谢金星.现代优化计算方法［M］.北京:清华大学出版社,2005.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
［关键词］ 军事物流 装载地域分配 遗传算法
装载地域保障是部队在军事物流过程中，以铁路为主要方式进行输送的重要物质和设备基础，是编制保障方案的重要内容之一。选择良好的具有保障部队不同进度条件下实施铁路输送能力的装载地域，对于保障部队安全、快速、正点地实施军事物流具有十分重要的意义。装载地域各装载点的优化分配方案可以有效地缩短部队的整体输送时间。长期以来，各装载站分配方案的制定，通常采用人工试探的方法，这种方法不仅费时费力，且经验型东西太多，具有很大的局限性，很难适应未来战时部队铁路输送的需要。因此，研究部队铁路输送保障中的装载地域分配问题的数学模型和求解算法，并应用于相关铁路军事运输辅助决策系统，是未来非线性战争中提高军交运输指挥效能的客观要求。
本文根据装载地域分配使用影响因素，建立了以对列车梯队分配装载站的总得分值为依据的装载地域分配模型，分析了该问题的复杂性，并设计了遗传算法来进行求解。
一、装载地域分配影响因素分析
铁路军事运输的装载需要在技术设备条件良好，运输组织方法适合的铁路车站上进行。在战役部队铁路输送时，由于部队驻地和到达装载地域的不同，为保证输送进度和序列实施，就需要选择多个铁路车站承担部队输送的装载作业，这些车站就构成了部队的装载地域。影响装载地域中装载站分配的因素很多，其中最主要的有以下几个：
1.装卸载能力。装卸载地域的装卸载能力是由该地域内各装卸载站的装卸载能力决定的。它的定义是：在一定的固定和活动设备以及装卸载和行车组织方法的条件下，一个装卸载地域在单位时间内（通常为一昼夜）所能装卸载的最大列车数。装卸载地域能力的大小，直接影响被运部队的输送进度和输送序列。
2.部队驻地与各装载站的距离。部队驻地距离装载站越远，部队的机动距离就越长，耗费也就越大。所以，应尽量选择离部队驻地近的装载站，这样可以减少部队的摩托化或徒步行进的距离，便于部队组织管理和进行各种保障。
3.部队输送进度。输送进度是指部队每昼夜按平均间隔发出的列车数。输送进度必须与装载地域的装载能力相匹配。
4.部队输送序列。输送序列是指各被运部队的开进顺序。
二、装载地域分配模型的建立
装载地域分配问题的描述为：在某个装载地域有n个装载站，待输送部队共有k个梯队，输送期限为m天，输送进度为P，问如何对各梯队分配装载站，使得满足输送序列和输送进度要求。
定义如下变量：
si表示第i个装载站；tj表示第j个梯队；表示车站i在第l天输送的列车梯队数，列；表示车站i的装载能力，列；表示第j个梯队离开装载地域的时间；P表示部队输送进度；表示梯队j选择车站i的得分值；
式(1)是目标函数，表示对列车梯队分配装载站的总得分值最大的那种分配方案；式(2)是装载能力限制，表示各装载站在任意一天内发出的列车数均不超过该装载站的装载能力；式(3)是输送序列限制，表示各列车梯队必须按输送序列发送；式(4)是输送进度限制，表示各装载站每天的装载列数都必须等于输送进度。
显然，所建立的模型是带有复杂约束的混合整数非线性规划模型，属于NP-hard问题。对于这类问题，传统的精确算法存在很多的局限性。比如说穷举法，它的时间复杂度为O(Nn)，N为问题的规模，n为运行次数。当N不断增大时，运行时间将迅速增加，如图所示。如果假设运算每一种分配方案所用时间为1s，那么计算3个装载站，30个梯队的部队输送装载站分配问题所花费的时间为6528765年。由此可看出大规模的部队输送装载站分配问题的复杂性。
三、遗传算法的设计
遗传算法起源于对生物系统所进行的计算机模拟研究。它具有实用、高效、鲁棒性强的特点，利用遗传算法可以得到问题的满意解。
1.设计染色体结构。为了提高效率，采用自然数编码，即序数编码。则装载地域分配的一条可行的染色体结构为（i1, i2,…, it,…, ik），t∈[1, k]且为自然数，it∈[1, n]且为自然数。k为待运部队的梯队数，n为装载地域内的车站数，it表示第t个列车梯队所选定的装载站。
2.确定初始种群。为了保证计算效率，群体规模不能太大，也不能太小，在这里规定群体规模取值为20到50之间。
3.确定适应度函数。适应度函数是由目标函数变换而成的。由于本文的目标是求对列车梯队分配总得分值最大的装载站，所以设计的适应度函数为： Fit(z) = z
4.设计遗传算子。对于选择算子，采用精英策略和随机竞争相结合的方法，在随机竞争选择时，每次按轮盘赌选择机制选取一对个体，然后让这一对个体进行竞争，适应度高的个体被选中，如此反复，直至选满为止。对于交叉算子，可采用两点交叉运算。变异算子采用对换变异。
5.设定终止条件。由于遗传算法具有较大的随机性，本文设计了2个终止条件：一是若迭代次数达到1000代；二是若最佳染色体连续保持10代。当遗传算法运算过程中满足任一个终止条件，就结束运算。
6.遗传算法的步骤
Step1：设置遗传算法的参数，即进化总迭代次数maxgen，种群规模popsize，交叉概率pc，变异概率pm；
Step2：进化迭代次数gen=0，随机产生popsize条染色体生成初始种群；
Step3：计算种群所有个体的适应度函数值；
Step4：选择操作，采用精英策略和轮盘赌的方法从群体中选择染色体作为父代染色体；
Step5：交叉操作，按照交叉概率对选择出的染色体进行交叉操作；
Step6：变异操作，按照变异概率对染色体进行变异操作；
Step7：不断进行遗传操作，直至生成的染色体的个数达到种群规模popsize，组成下一代群体，gen= gen+1；
Step8：如果gen>maxgen，算法结束，否则转Step3。
四、结束语
通过实验，对一个师规模部队，应用遗传算法在求解部队铁路输送装载地域分配问题时，可以在很短的时间内求得一个比较优的解。得到的装载站的分配使用方案是合理的，不仅满足装载地域分配的基本要求，同时也保证了部队的输送进度和输送序列。本文建立了贴合部队铁路输送装载地域分配的数学优化模型，并应用遗传算法对问题进行了求解。部队铁路输送中装载地域分配问题是典型的NP问题，随着问题规模的增加，优化搜索的计算量迅速增长，算法效率必然会下降。因此，在保证算法求解精度的前提下，进一步改进算法，提高算法的效率，是下一步的研究方向。
参考文献:
[1]鲍平鑫,徐开启.铁路军事运输［M］.北京:解放军出版社,2006.
[2]刘中,周飞飞,李海华.军运梯队铁路装载组合优化问题模拟退火算法研究［J］.军事交通学院学报,2010，(2)21-24。
[3]吴晓东.大规模部队铁路输送研究.北京交通大学博士论文,2008
[4]邢文训,谢金星.现代优化计算方法［M］.北京:清华大学出版社,2005.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文