物流運輸-路線區域的互斥問題
物流運輸一般是通過路線來的，但是考慮到實際場景，有可能具體城市的區與區之間是互斥的，不能放在同一條路線內，比如由於某一條較長的河分開了某些區域導致不能放一條路線內運輸；又比如運輸證是按照區域來發放的等等。
比如如下幾個節點：崑山(區：崑山市)、蘇州(區：相城區、吳中區)、佛山(區：順德區)、佛山(區：高明區) 這些節點城市+區域，我們假設：蘇州是個特別的城市，相城區、吳中區不能同時配在一條路線內部，求解
這個解最終是希望得到如下這樣的結果：
存在的解決方案個數：2
崑山(崑山市)--->蘇州(吳中區)--->佛山(順德區)--->佛山(高明區)--->
崑山(崑山市)--->蘇州(相城區)--->佛山(順德區)--->佛山(高明區)--->
這次用google的OR Tool來解決這個問題，鏈接在此處：//developers.google.cn/optimization
先定義數據結構，以及初始化demo數據
public static class CityLocation
{
public String cityName;
public String districtName;
public boolean special;
public CityLocation(String cityName, String districtName)
{
this(cityName, districtName, false);
}
public CityLocation(String cityName, String districtName, boolean special)
{
this.cityName=cityName;
this.districtName=districtName;
this.special=special;
}
}
private static List<CityLocation> generateData() {
List<CityLocation> result=new ArrayList<>();
CityLocation location=new CityLocation("崑山", "崑山市");
result.add(location);
location=new CityLocation("蘇州", "吳中區", true);
result.add(location);
location=new CityLocation("蘇州", "相城區", true);
result.add(location);
location=new CityLocation("佛山", "順德區");
result.add(location);
location=new CityLocation("佛山", "高明區");
result.add(location);
return result;
}
先說下思路，google的這個演算法框架，需要加入一堆約束，比如==約束、<=約束、<=約束等等，然後演算法框架會自己去窮舉；又或者做最優化，又或者做可行解（意思就是非最優化解）。
我們先來加約束：
static class SpecialCityRestrict implements LinearExpr
{
private List<IntVar> vars;
public SpecialCityRestrict(List<IntVar> vars) {
this.vars=vars;
}
@Override
public int numElements() {
return this.vars.size();
}
@Override
public IntVar getVariable(int i) {
return this.vars.get(i);
}
@Override
public long getCoefficient(int i) {
return 1;
}
}
//main方法里加
SpecialCityRestrict restrict=new SpecialCityRestrict(varsInner);
model.addLessOrEqual(restrict, 1);
model.addLessOrEqual就是加<=的約束，上述就是加了個<=1的約束，比如約束蘇州的區最多只能出現1次，也可以不出現的意思，<=1次
上方的List<IntVar> vars就是用來變換蘇州區是否被放入路線的控制變數，是個集合，會在main里放進去，如下：
List<CityLocation> globalCityLocations=generateData();
Map<String, List<IntVar>> specialCityVarsMap=new HashMap<>(); //特殊城市對應的or控制變數關係Map
List<String> specialCities=globalCityLocations.stream().filter(f->f.special).map(f->f.cityName).distinct().collect(Collectors.toList()); //篩選出所有特殊城市
for(String specialCity:specialCities)
specialCityVarsMap.put(specialCity, new ArrayList<>()); //初始化Map
CpModel model = new CpModel(); //or tool模型構建
List<IntVar> globalVars=new ArrayList<IntVar>(); //這裡會存放所有控制變數，後續會把這些控制變數傳入收集解決方案解的回調類中
for(int idx=0;idx<globalCityLocations.size();idx++)
{
IntVar var=model.newIntVar(0, 1, String.valueOf(idx)); //新建1個控制變數-int類型，值變化區間是[0, 1]
globalVars.add(var);
CityLocation cityLocation=globalCityLocations.get(idx);
if(cityLocation.special)
{
specialCityVarsMap.get(cityLocation.cityName).add(var); //如果是特殊城市，就把控制變數維護到特殊城市控制變數關係map中
specialCityVars.add(var);
}
}
for(String key:specialCityVarsMap.keySet()) //動態的從特殊城市map中開始加模型約束，不用寫死，很好
{
List<IntVar> varsInner=specialCityVarsMap.get(key);
SpecialCityRestrict restrict=new SpecialCityRestrict(varsInner); //針對某個具體特殊城市的約束對象
model.addLessOrEqual(restrict, 1); //對應的區的個數約束為<=1
}
然後就要搜索解決方案了
VarArraySolutionPrinter varArraySolutionPrinter=new VarArraySolutionPrinter(globalVars, globalCityLocations); //這個類是自定義的，用來收集解的集合的，在後面有定義
CpSolver solver = new CpSolver();
CpSolverStatus status=solver.searchAllSolutions(model, varArraySolutionPrinter);
System.out.println(status);
varArraySolutionPrinter.printSolutions();
static class VarArraySolutionPrinter extends CpSolverSolutionCallback {
private int solutionCount;
private List<IntVar> globalVars;
private List<CityLocation> globalCityLocations;
private List<List<CityLocation>> solutions=new ArrayList<>();
public VarArraySolutionPrinter(List<IntVar> globalVars, List<CityLocation> globalCityLocations) {
this.globalCityLocations=globalCityLocations;
this.globalVars=globalVars;
}
@Override
public void onSolutionCallback() {
List<CityLocation> oneSolution=new ArrayList<>();
for(int idx=0;idx<globalVars.size();idx++)
{
IntVar v=globalVars.get(idx);
long oneOrZero=value(v);
if(oneOrZero==1)
{
oneSolution.add(this.globalCityLocations.get(idx));
}
}
solutions.add(oneSolution);
solutionCount++;
}
public int getSolutionCount() {
return solutionCount;
}
public void printSolutions() {
System.out.println("存在的解決方案個數："+this.getSolutionCount());
for(List<CityLocation> oneSolution:this.solutions)
{
StringBuilder sb=new StringBuilder();
for(CityLocation cityLocation:oneSolution)
{
sb.append(cityLocation.cityName+"("+cityLocation.districtName+")--->");
}
System.out.println(" "+sb.toString());
}
System.out.println("--END--");
}
}
運行後的結果出乎意料：
OPTIMAL 存在的解決方案個數：24 蘇州(吳中區)---> 蘇州(相城區)---> 蘇州(相城區)--->佛山(順德區)---> 佛山(順德區)---> 蘇州(吳中區)--->佛山(順德區)---> 蘇州(吳中區)--->佛山(順德區)--->佛山(高明區)---> 佛山(順德區)--->佛山(高明區)---> 蘇州(相城區)--->佛山(順德區)--->佛山(高明區)---> 蘇州(相城區)--->佛山(高明區)---> 佛山(高明區)---> 蘇州(吳中區)--->佛山(高明區)---> 崑山(崑山市)--->蘇州(吳中區)--->佛山(高明區)---> 崑山(崑山市)--->蘇州(吳中區)--->佛山(順德區)--->佛山(高明區)---> 崑山(崑山市)--->蘇州(吳中區)--->佛山(順德區)---> 崑山(崑山市)--->蘇州(吳中區)---> 崑山(崑山市)---> 崑山(崑山市)--->佛山(順德區)---> 崑山(崑山市)--->佛山(順德區)--->佛山(高明區)---> 崑山(崑山市)--->佛山(高明區)---> 崑山(崑山市)--->蘇州(相城區)--->佛山(高明區)---> 崑山(崑山市)--->蘇州(相城區)---> 崑山(崑山市)--->蘇州(相城區)--->佛山(順德區)---> 崑山(崑山市)--->蘇州(相城區)--->佛山(順德區)--->佛山(高明區)---> --END--
似乎感覺不太對，得再加些約束啊，看來。
我們要求特殊城市必須出現在線路中，也就是說特殊城市節點的約束是>=1
在執行搜索的程式碼前加入這些程式碼：
SpecialCityRestrict specialCityMustExistsRestrict=new SpecialCityRestrict(specialCityVars); model.addGreaterOrEqual(specialCityMustExistsRestrict, 1);
然後再加個約束：非特殊城市必須出現在路線之中，也就是非特殊城市變換後選中為1的size要==非特殊城市的個數
SpecialCityRestrict normalCityRestrict=new SpecialCityRestrict(normalCityVars);
model.addEquality(normalCityRestrict, normalCityVars.size()); //這個normalCityVars需要改main里的循環，既：當為普通city時把控制變數add到這個List中
再執行下
OPTIMAL
存在的解決方案個數：2
崑山(崑山市)--->蘇州(吳中區)--->佛山(順德區)--->佛山(高明區)--->
崑山(崑山市)--->蘇州(相城區)--->佛山(順德區)--->佛山(高明區)--->
--END--
