024-ILOG-OPL的几个应用

ILOGOPL的几个应用一个经典的优化问题——TravelingSalesmanProblem有N个城市，已知每两个城市之间的距离，一个货郎要从城市1出发，依次经过所有的城市，最后返回城市1。如何走线路最短。如果把每两个城市之间的路径作为变量，以1代表经过该路径，0代表不经过该路径。则变量个数为N2个。很显然，每个城市的紧前城市和紧后城市只有一个，则包含约束数量为2N个。此外，必须保证只有唯一一条成环的路径，且该路径覆盖所有城市，这意味着所有的城市子集内部被选中的路径数量小于城市的数量。则包含约束数量为：12nmmnC2TSP问题的分析TSP是一个典型的NP-Hard问题，在给出一个顶点的网络（有向或无向），要求找出一个包含所有顶点的具有最小耗费的环路。环路被称为回路。故可以把任一个点作为起点（或终点）。如图所示：D场站客户点3TSP问题的数学模型4TSP问题的扩展VehicleRoutingProblem一个仓库向N个客户配送货物，每个客户都有各自的需求量，总需求量大于单车装载能力。已知仓库到各客户，以及客户之间的运输成本，如何以最少的车辆最少的运输成本满足客户的需求。5VRP问题的进一步扩展有多个仓库，多种吨位的卡车，向N1个客户送货，同时向N2个客户收货，每个客户要求到达时间在某个时间窗内，不同吨位的卡车所能通行的路段不同，不同时段各路段的平均行驶速度不同，不同客户的卸货速度有所不同。怎样分配不同的卡车到不同的线路，既能满足客户的要求，成本又相对最小。这样的问题适用于零售连锁企业的配送计划安排，也适用于快递行业的取件和送件计划。6VRP问题的分析场站客户点TSP问题跟VRP问题相比：所谓的旅行商问题简单而言为无车辆容量限制的“单一”路线客户服务组合问题而VRP则考虑车辆的容量限制，一般为多线路资源分配的问题，由于一个节点群只被一个资源占有，且每一个群线路规划方式相同，使得此问题的基本形态是旅行商问题。VRP如图所示：7跟TSP问题相比，在VRP中，最常见的附加条件有：1.承载能力约束。与每个节点对应的需求是个非负的值，任意车辆路径总重量不能超过该车辆的能力负荷。2.所含节点数目的上界为某个值。3.多个节点之间存在优先级，必须在访问的节点与另一个节点之间存在次序。4.总时间约束。也就是时间累积数目不能超过预先规定的某个值。5.时间窗口，我们把这个单个划分为VRPTW模型。因此，在求解VRP问题的时候，可以在TSP问题上加上适当的约束8目标体系：按照节点需求准时配送，同时运输工具在各个节点等待时间最少；使得运输总成本最低。所使用运输工具数目最少；使得行驶距离最短；以上目标之间互相联系，彼此影响，组成了一个目标体系。各个目标函数表达如下：VRP问题的模型9NiiiteMax0]0),[(MinAijkijkijxdMinBkyMinCijkijkijxdMinD最少运输费用：最少运输工具：最短距离：最少等待时间10DPCPBPAPE4321kNjjijkkkikNhjjhjkNhiiihkKkNjjijkKkNjijkqxmKyxxxKx1,01,0,011,01101],1[],1[],1[];,1[,...3,2,10KkKkKkNhNii多目标整数规划函数，设置优先系数P1，P2，P3，P4；VRP约束模型：约束条件1、2表示每个节点只能经过一次，而且每辆车都从出发点出发；约束条件3表示每个车辆到达一个需求点后，不能停留，必须离开；约束条件4表示配送车辆不能超过所有资源数目；约束条件5表示每一辆车有承载量限制。这些约束条件根据客观情况给予不同的含义，约束条件也随之增删变化11structConnection{Citieso;Citiesd;};structRoute{Connectione;Productsp;};structSupplier{Productsp;Citieso;};structCustomer{Productsp;Citiesd;};{Route}Routes=...;float+cost[Routes]=...;{Connection}Connections={c|c,pinRoutes};{Supplier}Suppliers={p,c.o|c,pinRoutes};float+supply[Suppliers]=...;{Customer}Customers={p,c.d|c,pinRoutes};float+demand[Customers]=...;enumCities...;enumProducts...;对VRP问题的OPL程序12structConnection{Citieso;Citiesd;};structRoute{Connectione;Productsp;};structSupplier{Productsp;Citieso;};structCustomer{Productsp;Citiesd;};{Route}Routes=...;{Connection}Connections={c|c,pinRoutes};{Supplier}Suppliers={p,c.o|c,pinRoutes};float+supply[Suppliers]=...;{Customer}Customers={p,c.d|c,pinRoutes};float+demand[Customers]=...;float+lim=...;float+cost[Routes]=...;{Cities}orig[pinProducts]={c.o|c,pinRoutes};{Cities}dest[pinProducts]={c.d|c,pinRoutes};{Connection}CP[pinProducts]={c|p,cinRoutes};assertforall(pinProducts)sum(oinorig[p])supply[p,o]=sum(dindest[p])demand[p,d];13varfloat+trans[Routes];minimizesum(rinRoutes)cost[r]*trans[r]subjectto{forall(pinProducts&oinorig[p])sum(o,dinCP[p])trans[o,d,p]=supply[p,o];forall(pinProducts&dindest[p])sum(o,dinCP[p])trans[o,d,p]=demand[p,d];forall(cinConnections)sum(c,pinRoutes)trans[c,p]=lim;};14一个测试TSP问题的实例客户点123456坐标值[38,20][16,24][40,15][63,24][52,43][30,35]客户点789101112坐标值[76,53][63,97][37,12][101,62][13,43][93,69]客户点131415161718坐标值[23,14][97,16][26,76][15,76][46,67][35,53]客户点192021222324坐标值[6,73][79,26][40,97][72,36][113,121][18,8]15求解结果TSP问题是一个简单的VRP问题，看着VRP问题的特例，输入数据，求解结果可以表示为如图：16一个VRP问题的例子supply=#[bandsGARY:400coilsGARY:800plateGARY:200bandsCLEV:700coilsCLEV:1600plateCLEV:300bandsPITT:800coilsPITT:1800platePITT:300]#;其余数据过多，此处省略一个仓库向N个客户配送货物，每个客户都有各自的需求量，总需求量大于单车装载能力。已知仓库到各客户，以及客户之间的运输成本，如何以最少的车辆最少的运输成本满足客户的需求。17OptimalSolutionwithObjectiveValue:199500.0000trans[#p:bands,e:#o:GARY,d:FRA##]=0.0000trans[#p:bands,e:#o:GARY,d:DET##]=0.0000trans[#p:bands,e:#o:GARY,d:LAN##]=0.0000trans[#p:bands,e:#o:GARY,d:WIN##]=0.0000trans[#p:bands,e:#o:GARY,d:STL##]=400.0000trans[#p:bands,e:#o:GARY,d:FRE##]=0.0000trans[#p:bands,e:#o:GARY,d:LAF##]=0.0000trans[#p:bands,e:#o:CLEV,d:FRA##]=225.0000trans[#p:bands,e:#o:CLEV,d:DET##]=0.0000trans[#p:bands,e:#o:CLEV,d:LAN##]=0.0000trans[#p:bands,e:#o:CLEV,d:WIN##]=0.0000trans[#p:bands,e:#o:CLEV,d:STL##]=250.0000trans[#p:bands,e:#o:CLEV,d:FRE##]=0.000018trans[#p:bands,e:#o:CLEV,d:LAF##]=225.0000trans[#p:bands,e:#o:PITT,d:FRA##]=75.0000trans[#p:bands,e:#o:PITT,d:DET##]=300.0000trans[#p:bands,e:#o:PITT,d:LAN##]=100.0000trans[#p:bands,e:#o:PITT,d:WIN##]=75.0000trans[#p:bands,e:#o:PITT,d:STL##]=0.0000trans[#p:bands,e:#o:PITT,d:FRE##]=225.0000trans[#p:bands,e:#o:PITT,d:LAF##]=25.0000trans[#p:coils,e:#o:GARY,d:FRA##]=0.0000trans[#p:coils,e:#o:GARY,d:DET##]=0.0000trans[#p:coils,e:#o:GARY,d:LAN##]=0.0000trans[#p:coils,e:#o:GARY,d:WIN##]=0.0000trans[#p:coils,e:#o:GARY,d:STL##]=25.0000trans[#p:coils,e:#o:GARY,d:FRE##]=625.0000trans[#p:coils,e:#o:GARY,d:LAF##]=150.0000trans[#p:coils,e:#o:CLEV,d:FRA##]=0.0000trans[#p:coils,e:#o:CLEV,d:DET##]=525.0000trans[#p:coils,e:#o:CLEV,d:LAN##]=400.0000trans[#p:coils,e:#o:CLEV,d:WIN##]=250.0000trans[#p:coils,e:#o:CLEV,d:STL##]=300.000019trans[#p:coils,e:#o:CLEV,d