文档介绍：UTLogo100Stochastic ProgrammingSchool of Management, UCASVehicle Routing ProblemKai YaoSchool of Management, UCASKai ******@ ProgrammingSchool of Management, UCASVehicle Routing Problemvehicledepotcustomertime windowtravel timetravel distanceVehicle routing problem (VRP) is concerned with ?nding e?cient routes,beginning and ending at a central depot, for a ?eet of vehicles to serve anumber of ******@ ProgrammingSchool of Management, UCASFormulationx= (x1,x2,· · ·,xn): integer decision vector representingncustomers with1≤xi≤nandxi6=xjfor alli6=j,i,j= 1,2,· · ·,= (y1,y2,· · ·,ym?1): integer decision vector withy0≡0≤y1≤y2≤· · · ≤ym?1≤n≡ym;t= (t1,t2,· · ·,tm): eachtkrepresents the starting time of =yk?1, then vehiclekis not used;ifyk>yk?1, then vehiclek:0→xyk?1+1→xyk?1+2→· · · →xyk→ ******@ k是快递员,若快递员1和快递员2访问的顾客一样,则没必要要快递员2 =2,快递员2,从0出发,再到x3-x4-x5-0(回到原点)UTLogo100Stochastic ProgrammingSchool of Management, UCASRandom Travel TimesTij: travel time from customersitojΦij: probability distribution ofTij所有车都是同质性假设Kai ******@ ProgrammingSchool of Management, UCASArrival Time Function —First CustomerVehiclek: 0→xyk?1+1→xyk?1+2→· · · →xyk→0Starting TimestkThe arrival time function at the ?rst customerxyk?1+1isfxyk?1+1(x,y,t) =tk+T0xyk?1+ ******@ ProgrammingSchool of Management, UCASArrival Time Function —Second CustomerVehiclek: 0→xyk?1+1→xyk?1+2→· · · →xyk→0Starting TimestkThe arrival time function at the second customerxyk?1+2isfxyk?1+2(x,y,t) =fxyk?1+1(x,y,t)∨axyk?1+1+Txyk?1+1xyk?1+ ******@ 完成第一个顾客任务花费时间离开第一个顾客,到达第二个顾客花费的时间UTLogo100Stochastic ProgrammingSchool of Management, UCASArrival Time Function —Last CustomerVehiclek: 0→xyk?1+1→xyk?1+2→· · · →xyk→0Starting TimestkThe arrival time function at the last customerxykisfxyk(x,y,t) =fxyk?1(