cost = cell[2][sat_num] % traveling cost
基于距离的贪婪法则将每个客户分配给一个卫星,完成初始解计算。
- 将每个客户按照需求递减的顺序排序
- 将每个客户分配到相应的卫星,按照距离最近的原则
- 如果将某个客户分配给卫星时,意味着需要额外增加一辆车辆,则需要检查整个车辆容量是否被违反。如果是的话,这个分配解不可行,客户应当被分配到第二个最近的卫星,直到找到一个可行解。
采用遗传算法解决Ns+1个CVRP问题。
- 初始化,随机选择一些个体选择最初的种群。
- 评估,通过某种方法来评估个体的适应度(生存能力)。路线越短越好。
- 选择,类似于自然选择,优良的基因,生存能力强的被选择下来的概率要大。采用 最佳个体保存与赌轮相结合 的选择策略。其具体操作为:将每代群体中的N个个体按适应度由小到达排列,排在首位的个体性能最好,将它直接复制到下一代。下一代群体的令N-1个体需要根据上一代群体的N个个体的适应度采用赌轮选择。
- 交叉,产生后代,基因交叉。
- 变异,后代的基因可能会变异,变异在生物进化中起了很大作用。
选择、交叉、变异是产生新种群的步骤,新种群再进行评估,直至找到一个近似最优解。
基于FC的解,每次改变一个客户-卫星分配关系。
鉴于目前最好的解,根据规则(考虑重组花费)对客户-卫星分配关系进行扰乱。
如果新的解不是可行解,使用可行解搜索算法获得新的可行解。
如果新的解是可行解,执行CI阶段。