深圳自动驾驶创业公司（2022深圳杯C题自动驾驶电动物料车换电站选址及调度方案）

2022深圳杯C自动驾驶电动物料车换电站选址及调度方案

  为了实现我国在 2030 年前“碳达峰  
    
    
”    
    
    、在 2060 年前“碳中和

     


     


    ”的目标    
    
    ，在物料运输中使用环保的自动驾驶电动车是发展趋势    
    
    。在制订电动车调度方案时   


     


     


，必须考虑充   


     


     


、换电池的时间成本



 




 




，从而提出了新的车辆运输选址及调度问题   


     


     


。

  问题 1 一批自动驾驶电动物料车将物料从 P 点运送到 D 点   

   

   ，然后空载返回    

     

     

，

如此循环往复运送物料



 




 




。要求建立数学规划模型




  




  




，在 P 点与 D 点之间确定一个双向同址（像高速的休息站一样）的换电站位置  


  


  ，以及对应的车辆和电池组调度方案     
     
     
，极大化指定时间段内运送物料量




   




   




，满足资源约束与电池运行方式约束   

   

   。根据附录所给的数据
 



 



 ，求解规划模型               ，给出换电站位置 




    




    




，并给出在 1000 小时中运送的物料量











，所使用车辆



 




 




、电池组数量和车辆及其各电池组的具体调度方案    

     

     

。

  问题 2 在问题 1 中               ，将建站条件更改成为“在 P 点与 D 点之间每个方向分别确定一个换电站位置 




 




 


”  



     



     



，其他条件与任务与问题 1 相同




  




  




。

  问题 3 考虑峰谷电价   

   

   、购置电池组    

     

     

、建设充




  




  




、换电站等成本












，制定保证每日最低运输量    
    
    ，3 年结算周期投资运行成本最低的建站及电池组调度方案  


  


  。根据附录所给的数据（缺省的数据自行补充）   


     


     


，给出具体算例     
     
     
。问题 4 对多个取料点  


  


  、单个卸货点



 




 




，研究上述换电站选址及车辆-电池组调度问题




   




   




。

附录：数据格式（限定）

算例数据在下列格式限定下自行编制   

   

   ，决赛前将发布统一测试算例数据
 



 



 。

  (1) P 点到 D 点：里程 10 km    

     

     

，双向单车（轨）专用道




  




  




，车距不小于 200 m

  (2) 车辆：125 辆  


  


  ，速率 60 km/h, 每车额定装配 6 个电池组     
     
     
，初始位于换电站空载状态




   




   




，且每个车载电池组的 SoC（荷电状态）都是 100%

  (3) 电池：900 组
 



 



 ，单个电池组独立计量               ，车载 6 个电池组一致消耗电量 




    




    




，空载车辆每行驶 3 分钟每个电池组的 SoC 都减少 1%











，载货车辆每行驶 2 分钟每个电池组的 SoC 都减少 1%               ，车载电池组的 SoC 位于区间[10%,25%]时方可更换  



     



     



，备更换电池组的 SoC 为 100%

  (4) 耗时：每更换一个电池组耗时 20 秒












，每个电池组更换下来后充电     
     
     
、检测进入备用状态总耗时 3 小时    
    
    ，装卸货每次各需要 1 分钟

  (5) 价格：峰谷电价   


     


     


，换电站地价



 




 




，充电速率及充电桩造价   

   

   ，自动换电池设备价格    

     

     

，电池价格




  




  




，车辆价格               。

模型的建立与求解分析：

  首先考虑这个题是从换电站到P点到D点再到P点直到电池容量到10%至25%的时候  


  


  ，到换电站进行电池更换

  这里可以画一个线路图

  S双行道的长度为10km也就是10000m

  每两车距大于等于200m     
     
     
，什么意思？

在不考虑车长情况下 公路上最多奔驰100辆电车

题中说电池：900 组




   




   




，单个电池组独立计量
 



 



 ，车载 6 个电池组一致消耗电量 




    




    




。

  我这智商余额不足               ，我不考虑6个电池分批充电分批换电池的情况了 




    




    




，我直接在模型的假设中写：假设电车换电池6个电池组一起换











，忽略单个电池单独换对于总体货载量的影响











。

  又是电池组合分批换电又是考虑换电站的位置




   




   




、货运总量最大
 



 



 、时间1000h=60000min内               ，6个电池用到贴近10%一起换和分批换的区别我知道会影响整体900组电池的使用率  



     



     



，但这个电池换电方案不好算               。这题的意思就是让你拿整数规划和线性规划的组合












，道上跑着100辆电车然后其余的电池尽量没有浪费都在充电    
    
    ，然后这车跑的快到10%的时候电池正好充完了   


     


     


，以此循环往复



 




 




，问你换电站建哪？换电池怎么换？能达到货运量最大  



     



     



。

  我说一下为什么电站位置好算而电池换电分配方案不好算   

   

   ，这是因为6块电池你如果换电池的方案的话有C6选1也就是说6种电池换电方案    

     

     

，然后你通过对比或是智商碾压得出最优的电池换电方案




  




  




，为什么是6种方案呢？因为25%-10%=15%的电量能跑一来回加一个去或者回的电量  


  


  ，但是你还得保证有去换电站的电量剩余     
     
     
，所以说第二趟你去不了了




   




   




，只能老实换电
 



 



 ，懂了么












。

最终结果

  第一问最后你确定换电站是在P去D的5km处建立换电站    
    
    。至于电池换电方案               ，你猜猜你就合计怎么整电池利用效率最大？运输量之与车数               、电车到达P的次数有关 




    




    




，而电池影响车数和到达P的次数











，亲爱的读者你转过来这个弯了么？

  第二问最后结果是在去和回的20/3km处建换电站   


     


     


。

  第三问结果需考虑换点的时间点 白天怎么换 夜晚怎么换 使用工业用电时间最低价格 与最高价格的换电策略方案

  第四问结果需考虑排队论算法

  思路终于完成了 欢迎打扰

以上仅代表个人对于该题的理解

程序代码示例：

import math # 导⼊模块 import random # 导⼊模块 import pandas as pd # 导⼊模块 YouCans, XUPT import numpy as np # 导⼊模块 numpy               ，并简写成 np import matplotlib.pyplot as plt from datetime import datetime # ⼦程序：定义优化问题的⽬标函数 def cal_Energy(X, nVar, mk): # m(k)：惩罚因⼦  



     



     



，随迭代次数 k 逐渐增⼤ p1 = (max(0, 6*X[0]+5*X[1]-60))**2 p2 = (max(0, 10*X[0]+20*X[1]-150))**2 fx = -(10*X[0]+9*X[1]) return fx+mk*(p1+p2) # ⼦程序：模拟退⽕算法的参数设置 def ParameterSetting(): cName = "funcOpt" # 定义问题名称 YouCans, XUPT nVar = 2 # 给定⾃变量数量












，y=f(x1,..xn) xMin = [0, 0] # 给定搜索空间的下限    
    
    ，x1_min,..xn_min xMax = [8, 8] # 给定搜索空间的上限   


     


     


，x1_max,..xn_max tInitial = 100.0 tFinal = 1 alfa = 0.98 meanMarkov = 100 # Markov链长度



 




 




，也即内循环运⾏次数 scale = 0.5 # 定义搜索步长   

   

   ，可以设为固定值或逐渐缩⼩ return cName, nVar, xMin, xMax, tInitial, tFinal, alfa, meanMarkov, scale # 模拟退⽕算法 def OptimizationSSA(nVar,xMin,xMax,tInitial,tFinal,alfa,meanMarkov,scale): # ====== 初始化随机数发⽣器 ====== randseed = random.randint(1, 100) random.seed(randseed) # 随机数发⽣器设置种⼦    

     

     

，也可以设为指定整数 # ====== 随机产⽣优化问题的初始解 ====== xInitial = np.zeros((nVar)) # 初始化




  




  




，创建数组 for v in range(nVar): # xInitial[v] = random.uniform(xMin[v], xMax[v]) # 产⽣ [xMin, xMax] 范围的随机实数 xInitial[v] = random.randint(xMin[v], xMax[v]) # 产⽣ [xMin, xMax] 范围的随机整数 # 调⽤⼦函数 cal_Energy 计算当前解的⽬标函数值 fxInitial = cal_Energy(xInitial, nVar, 1) # m(k)：惩罚因⼦  


  


  ，初值为 1 # ====== 模拟退⽕算法初始化 ====== xNew = np.zeros((nVar)) # 初始化     
     
     
，创建数组 xNow = np.zeros((nVar)) # 初始化




   




   




，创建数组 xBest = np.zeros((nVar)) # 初始化
 



 



 ，创建数组 xNow[:] = xInitial[:] # 初始化当前解               ，将初始解置为当前解 xBest[:] = xInitial[:] # 初始化最优解 




    




    




，将当前解置为最优解 fxNow = fxInitial # 将初始解的⽬标函数置为当前值 fxBest = fxInitial # 将当前解的⽬标函数置为最优值 print(x_Initial:{:.6f},{:.6f},\tf(x_Initial):{:.6f}.format(xInitial[0], xInitial[1], fxInitial)) recordIter = [] # 初始化











，外循环次数 recordFxNow = [] # 初始化               ，当前解的⽬标函数值 recordFxBest = [] # 初始化  



     



     



，最佳解的⽬标函数值 recordPBad = [] # 初始化












，劣质解的接受概率 kIter = 0 # 外循环迭代次数 totalMar = 0 # 总计 Markov 链长度 totalImprove = 0 # fxBest 改善次数 nMarkov = meanMarkov # 固定长度 Markov链 # ====== 开始模拟退⽕优化 ====== # 外循环 tNow = tInitial # 初始化当前温度(current temperature) while tNow >= tFinal: # 外循环 kBetter = 0 # 获得优质解的次数 kBadAccept = 0 # 接受劣质解的次数 kBadRefuse = 0 # 拒绝劣质解的次数 # ---内循环    
    
    ，循环次数为Markov链长度 for k in range(nMarkov): # 内循环   


     


     


，循环次数为Markov链长度 totalMar += 1 # 总 Markov链长度计数器 # ---产⽣新解 # 产⽣新解：通过在当前解附近随机扰动⽽产⽣新解



 




 




，新解必须在 [min,max] 范围内 # ⽅案 1：只对 n元变量中的⼀个进⾏扰动   

   

   ，其它 n-1个变量保持不变 xNew[:] = xNow[:] v = random.randint(0, nVar-1) # 产⽣ [0,nVar-1]之间的随机数 xNew[v] = round(xNow[v] + scale * (xMax[v]-xMin[v]) * random.normalvariate(0, 1)) # 满⾜决策变量为整数    

     

     

，采⽤最简单的⽅案：产⽣的新解按照四舍五⼊取整 xNew[v] = max(min(xNew[v], xMax[v]), xMin[v]) # 保证新解在 [min,max] 范围内 # ---计算⽬标函数和能量差 # 调⽤⼦函数 cal_Energy 计算新解的⽬标函数值 fxNew = cal_Energy(xNew, nVar, kIter) deltaE = fxNew - fxNow # ---按 Metropolis 准则接受新解 # 接受判别：按照 Metropolis 准则决定是否接受新解 if fxNew < fxNow: # 更优解：如果新解的⽬标函数好于当前解




  




  




，则接受新解 accept = True kBetter += 1 else: # 容忍解：如果新解的⽬标函数⽐当前解差  


  


  ，则以⼀定概率接受新解 pAccept = math.exp(-deltaE / tNow) # 计算容忍解的状态迁移概率 if pAccept > random.random(): accept = True # 接受劣质解 kBadAccept += 1 else: accept = False # 拒绝劣质解 kBadRefuse += 1 # 保存新解 if accept == True: # 如果接受新解     
     
     
，则将新解保存为当前解 xNow[:] = xNew[:] fxNow = fxNew if fxNew < fxBest: # 如果新解的⽬标函数好于最优解




   




   




，则将新解保存为最优解 fxBest = fxNew xBest[:] = xNew[:] totalImprove += 1 scale = scale*0.99 # 可变搜索步长
 



 



 ，逐步减⼩搜索范围               ，提⾼搜索精度 # ---内循环结束后的数据整理 # pBadAccept = kBadAccept / (kBadAccept + kBadRefuse) # 劣质解的接受概率 recordIter.append(kIter) # 当前外循环次数 recordFxNow.append(round(fxNow, 4)) # 当前解的⽬标函数值 recordFxBest.append(round(fxBest, 4)) # 最佳解的⽬标函数值 recordPBad.append(round(pBadAccept, 4)) # 最佳解的⽬标函数值

思路终于完成了 欢迎打扰