毕业前夕，我把研究生期间的研究基础整理好，以便以后能及时捡起来。 写了一部分，剩下的继续更新。
1 .旅行者问题旅行者问题(Traveling Salesman Problem，TSP )，又称货郎担问题，是图论中典型的组合优化问题。 经典的TSP可以描述为一个商品的推销员要去几个城市卖商品。 那个推销员要从一个城市出发，必须经过所有城市一次，然后只返回一次出发城市。 为了使他走过的总路程最短，他问应该如何选择城市之间的旅行路线。
从图论的角度看，这个问题其实是在赋权的无向图中去寻找哈密顿回路，并且使该回路的总权重最小。
很容易看出旅行者问题的可行解是n个顶点的全部排列(打乱[ 1，2，3，4，N]并随机排列)，其可行解的个数为(N-1 )！ 个，也就是说路线有(N-1 )！ 个。
此处介绍了如何建模(请参阅基于2014Lingo的旅行者问题建模方法) :
型号1 :
标记为赋能图g=(v，e )，v为顶点集合，e为边集合，各顶点之间的距离dij是已知的，n为城市数。
模型变量：
指示是否选择了从I访问j的弧
最小(1.1 )。
STT.() 1.2 )。
(1.3 ) )。
(1.4 )。
(1.5 ) )。
Note::)包含符号，前后两个集合可以相等。 真正包含符号是指，将1.4个即n个城市划分为任意非空的两组s后，限制可行的旅行路线存在至少一个以s中的某市I为起点、中的某城j为终点的行程。
(1.1 )表示最小化路径成本(1.2 )表示每个城市点必须出一次； (1.3 )表示各城市点必须进入一次； (1.4 )表示消除了部分循环的限制，s是除去了v集合的空集合的真子集，对于任意的真子集，为了满足该限制，不发生部分循环；
上图显示了在不添加子电路的情况下解除约束可能发生的情况，但还有两种解除子电路的显示。
型号2 :
(1.1 ) () 1.3 ) )。
(2.6 ) )。
意味着不对任意数量的1到V-1的点构成电路
模型3 ) mtz约束消除子循环) :
(1.1 ) () 1.3 ) )。
(2.7 ) )。
(2.8 ) )。
这种约束除了起点外，作为辅助变量没有实际意义，这种形式在求解模型时效率最高。
2 .车辆路径问题(VRP ) http://www.Sina.com/(VRP )于1959年由Dantzig和Ramser首次提出。 这是指一定数量的客户，各有不同数量的货物需求，配送中心为客户提供货物，由一个团队负责货物配送，组织合适的行驶路线。 3358www.Sina.com/可以满足客户的需求，在一定的约束下，达到例如车辆路径问题等目的。
le="margin-left:0cm;"> 2.1 带有容量约束的车辆路径问题(CVRP)该模型很难拓展到VRP的其他场景,并且不知道具体车辆的执行路径，因此对其模型继续改进。
2.2 带有多车场的车辆路径问题(MDVRP)参考(2005 lim，多车场车辆路径问题的遗传算法_hxdfn, 1996 renaud)
定义：
由于车辆是同质的，这里的建模在变量中没有加入车辆的维度。
2.3 带时间窗的车辆路径问题(VRPTW)由于VRP问题的持续发展，考虑需求点对于车辆到达的时间有所要求之下，在车辆途程问题之中加入时窗的限制，便成为带时间窗车辆路径问题（VRP with Time Windows, VRPTW）。带时间窗车辆路径问题（VRPTW）是在VRP上加上了客户的被访问的时间窗约束。在VRPTW问题中，除了行驶成本之外, 成本函数还要包括由于早到某个客户而引起的等待时间和客户需要的服务时间。在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同。
模型1问题定义：
The VRPTW is defined by a fleet of vehicles K={1,…,k} , a set of customers C={1,…,n} , and a directed graph G, Typically the fleet is considered to be homogeneous, that is, all vehicles are identical. The graph consists of |C| + 2 vertices, where the customers are denoted 1, 2,...,n and the depot is represented by the vertices 0 ("the starting depot") and n + 1 ("the returning depot"). The set of all vertices, that is, 0,1,... , n+1 is denoted N. The set of arcs, A, represents direct connections between the depot and the customers and among the customers. There are no arcs ending at vertex 0 or originating from vertex n + 1. With each arc (i,j), where i≠j , we associate a cost cij and a time tij , which may include service time at customer i.
Each vehicle has a capacity Q and each customer i a demand qi . Each customer i has a time window [ai,bi] and a vehicle must arrive at the customer before bi . If it arrives before the time window opens, it has to wait until ai to service the customer. The time windows for both depots are assumed to be identical to [a0,b0] which represents the scheduling horizon. The vehicles may not leave the depot before a0 and must return at the latest at time bn+1 .
It is assumed that Q, ai , bi , qi , cij are non-negative integers and tij are positive integers. Note that this assumption is necessary to develop an algorithm for the shortest path with resource constraints used in the column generation approach presented later. Furthermore it is assumed that the triangle inequality is satisfied for both cij and tij .
The decision variable s ik is defined for each vertex i and each vehicle k and denotes the time vehicle k starts to service customer i. In case vehicle k does not service customer i, s ik has no meaning and consequently it's value is considered irrelevant. We assume a0 = 0 and therefore s 0k = 0, for all k.
模型2(参考2017 A generalized formulation for vehicle routing problems)：
该模型为2维决策变量
2.4 VRP with BackhaulsThe Vehicle Routing Problem with Backhauls (VRPB) is a VRP in which customers can demand or return some commodities. So in VRPPD it’s needed to take into account that the goods that customers return to the deliver vehicle must fit into it. The critical assumption in that all deliveries must be made on each route before any pickups can be made. This arises from the fact that the vehicles are rear-loaded, and rearrangement of the loads on the tracks at the delivery points is not deemed economical or feasible. The quantities to be delivered and picked-up are fixed and known in advance. VRPB is similar to VRPPD with the restriction that in the case of VRPB all deliveries for each route must be completed before any pickups are made.
在VRPB问题中，车辆从起点出发访问一系列客户进行送货，然后接着访问一系列客户装载货物，之后回到起点。该问题的一个关键假设是车辆必须完成送货过程然后再访问顾客进行装货。