物流運輸-最小化門店個數問題
- 2020 年 8 月 15 日
- 筆記
- logistics-elimination
例如，有一批食材要發到肯德基門店，分別分配給了2個司機去送貨，如下：
都從上海出發 2個司機 第一個司機： 蘇州 新蘇站餐廳、園區車坊餐廳 無錫 高鐵無錫東站餐廳、無錫城際餐廳 第二個司機： 無錫 海岸城餐廳、無錫城際餐廳、大潤發 餐廳 常州 常州百貨大樓餐廳、常州城際 餐廳
某位調度大哥一看，都經過無錫，還都要往「無錫城際餐廳」送貨，感覺重複了，不能合併？現在2位司機的送貨門店個數分別是4個門店以及5個門店，能不能縮減下（由於發現了公共門店，因此縮減門店數變成了可能）
對於這個問題，我們首先不考慮貨物能不能裝上同一輛車這種容量問題，先考慮門店合併問題，其次考慮容量問題。此文中只說門店合併問題。
和上篇的風格一樣，先貼出我們期望的output：
------------原始組合------------- 第一個司機： 4個門店 full: 新蘇站餐廳,園區車坊餐廳,高鐵無錫東站餐廳,無錫城際餐廳, fixed: 新蘇站餐廳,園區車坊餐廳, dynamic: 高鐵無錫東站餐廳,無錫城際餐廳, 第二個司機： 5個門店 full: 常州百貨大樓餐廳,常州城際 餐廳,海岸城餐廳,無錫城際餐廳,大潤發 餐廳, fixed: 常州百貨大樓餐廳,常州城際 餐廳, dynamic: 海岸城餐廳,無錫城際餐廳,大潤發 餐廳, -------------移動組合------------- 第一個司機（5個門店）：新蘇站餐廳, 海岸城餐廳, 高鐵無錫東站餐廳, 園區車坊餐廳, 大潤發 餐廳, 第二個司機（3個門店）：常州城際 餐廳, 無錫城際餐廳, 常州百貨大樓餐廳, 從第一個司機move到第二個司機的：無錫城際餐廳, 從第二個司機move到第一個司機的：海岸城餐廳, 大潤發 餐廳, 第一個司機（3個門店）：新蘇站餐廳, 無錫城際餐廳, 園區車坊餐廳, 第二個司機（5個門店）：常州城際 餐廳, 海岸城餐廳, 高鐵無錫東站餐廳, 常州百貨大樓餐廳, 大潤發 餐廳, 從第一個司機move到第二個司機的：海岸城餐廳, 從第二個司機move到第一個司機的：無錫城際餐廳, 第一個司機（5個門店）：新蘇站餐廳, 海岸城餐廳, 無錫城際餐廳, 園區車坊餐廳, 大潤發 餐廳, 第二個司機（3個門店）：常州城際 餐廳, 高鐵無錫東站餐廳, 常州百貨大樓餐廳, 從第一個司機move到第二個司機的：海岸城餐廳, 從第二個司機move到第一個司機的：海岸城餐廳, 無錫城際餐廳, 大潤發 餐廳, 第一個司機（3個門店）：新蘇站餐廳, 海岸城餐廳, 園區車坊餐廳, 第二個司機（5個門店）：常州城際 餐廳, 高鐵無錫東站餐廳, 無錫城際餐廳, 常州百貨大樓餐廳, 大潤發 餐廳, 從第一個司機move到第二個司機的：海岸城餐廳, 無錫城際餐廳, 從第二個司機move到第一個司機的：海岸城餐廳, 第一個司機（3個門店）：新蘇站餐廳, 園區車坊餐廳, 大潤發 餐廳, 第二個司機（5個門店）：常州城際 餐廳, 海岸城餐廳, 高鐵無錫東站餐廳, 無錫城際餐廳, 常州百貨大樓餐廳, 從第一個司機move到第二個司機的：海岸城餐廳, 無錫城際餐廳, 從第二個司機move到第一個司機的：大潤發 餐廳, -------------SUMMARY------------- OPTIMAL 有效移動組合個數：5
解題思路：
首先判讀這個問題的類型，目測來看數據量較小，不存在窮舉非常耗時這種問題，因此首選採用確定性算法，而不是非確定性算法（遺傳算法、粒子算法這種是非確定的，每次執行都會變，特別是數據量大的時候）
既然選擇確定性算法&&數據量小，因此就窮舉組合了，按照上面的城市組合，又分成了固定與動態的城市區分。固定代表這個城市內的門店是不可調整的，動態代表這個城市內的門店是可調整的，可調整代表可以與其他司機的同城市的門店進行互換操作，其實區分固定與動態城市後，算法的數據量會進一步減小，因為只要窮舉動態城市部分就行了。
public static void main(String[] args) {
List<ReceiverItem> leftItems=generateData(ListUtils.newList("新蘇站餐廳", "園區車坊餐廳"), ListUtils.newList("高鐵無錫東站餐廳", "無錫城際餐廳"));
List<ReceiverItem> rightItems=generateData(ListUtils.newList("常州百貨大樓餐廳", "常州城際 餐廳"), ListUtils.newList("海岸城餐廳", "無錫城際餐廳", "大潤發 餐廳"));
List<IntVar> leftFixedVars=new ArrayList<>();
List<IntVar> leftExchangableVars=new ArrayList<>();
List<IntVar> rightFixedVars=new ArrayList<>();
List<IntVar> rightExchangableVars=new ArrayList<>();
CpModel model = new CpModel();
//第一個司機
for(ReceiverItem receiverItem:leftItems)
{
if(!receiverItem.exchangable)
{
//不可以交換，因此固定為第一個司機
IntVar var=model.newConstant(1);
leftFixedVars.add(var);
}
else
{
IntVar var=model.newIntVar(1, 2, "");
leftExchangableVars.add(var);
}
}
//第二個司機
for(ReceiverItem receiverItem:rightItems)
{
if(!receiverItem.exchangable)
{
//不可以交換，因此固定為第二個司機
IntVar var=model.newConstant(2);
rightFixedVars.add(var);
}
else
{
IntVar var=model.newIntVar(1, 2, "");
rightExchangableVars.add(var);
}
}
VarArraySolutionPrinter varArraySolutionPrinter=new VarArraySolutionPrinter(leftItems, rightItems, leftFixedVars, leftExchangableVars, rightFixedVars, rightExchangableVars);
CpSolver solver = new CpSolver();
System.out.println("------------原始組合-------------");
PrintUtils.display組合("第一個司機：", leftItems);
PrintUtils.display組合("第二個司機：", rightItems);
System.out.println("-------------移動組合-------------");
CpSolverStatus status=solver.searchAllSolutions(model, varArraySolutionPrinter);
System.out.println("-------------SUMMARY-------------");
System.out.println(status);
List<MoveAction> moveActions=varArraySolutionPrinter.getMoveActions();
System.out.println("有效移動組合個數："+moveActions.size());
}
static class VarArraySolutionPrinter extends CpSolverSolutionCallback {
private List<ReceiverItem> leftItems;
private List<ReceiverItem> rightItems;
private List<IntVar> leftFixedVars;
private List<IntVar> leftExchangableVars;
private List<IntVar> rightFixedVars;
private List<IntVar> rightExchangableVars;
private List<MoveAction> moveActions=new ArrayList<>();
public List<MoveAction> getMoveActions()
{
return this.moveActions;
}
public VarArraySolutionPrinter(List<ReceiverItem> leftItems, List<ReceiverItem> rightItems, List<IntVar> leftFixedVars, List<IntVar> leftExchangableVars, List<IntVar> rightFixedVars, List<IntVar> rightExchangableVars) {
this.leftItems=leftItems;
this.rightItems=rightItems;
this.leftFixedVars=leftFixedVars;
this.leftExchangableVars=leftExchangableVars;
this.rightFixedVars=rightFixedVars;
this.rightExchangableVars=rightExchangableVars;
}
@Override
public void onSolutionCallback() {
Set<String> leftReceivers=new HashSet<>();
Set<String> rightReceivers=new HashSet<>();
List<String> originalleft=new ArrayList<>();
List<String> move2left=new ArrayList<>();
List<String> originalright=new ArrayList<>();
List<String> move2right=new ArrayList<>();
//left fixed
for(int idx=0;idx<leftFixedVars.size();idx++)
{
leftReceivers.add(leftItems.get(idx).name);
}
//left exchangable
for(int idx=0;idx<leftExchangableVars.size();idx++)
{
IntVar var=leftExchangableVars.get(idx);
long v=value(var);
if(v==1)
{
leftReceivers.add(leftItems.get(idx+leftFixedVars.size()).name);
originalleft.add(leftItems.get(idx+leftFixedVars.size()).name);
}
}
for(int idx=0;idx<rightExchangableVars.size();idx++)
{
IntVar var=rightExchangableVars.get(idx);
long v=value(var);
if(v==1)
{
leftReceivers.add(rightItems.get(idx+rightFixedVars.size()).name);
move2left.add(rightItems.get(idx+rightFixedVars.size()).name);
}
}
//right fixed
for(int idx=0;idx<rightFixedVars.size();idx++)
{
rightReceivers.add(rightItems.get(idx).name);
}
//right exchangable
for(int idx=0;idx<leftExchangableVars.size();idx++)
{
IntVar var=leftExchangableVars.get(idx);
long v=value(var);
if(v==2)
{
rightReceivers.add(leftItems.get(idx+leftFixedVars.size()).name);
move2right.add(rightItems.get(idx+rightFixedVars.size()).name);
}
}
for(int idx=0;idx<rightExchangableVars.size();idx++)
{
IntVar var=rightExchangableVars.get(idx);
long v=value(var);
if(v==2)
{
rightReceivers.add(rightItems.get(idx+rightFixedVars.size()).name);
originalright.add(rightItems.get(idx+rightFixedVars.size()).name);
}
}
if(leftReceivers.size()<=5&&rightReceivers.size()<=5&&(leftReceivers.size()<=3||rightReceivers.size()<=3))//最終窮舉出來的要滿足的約束
{
if(move2left.size()>0&&move2right.size()>0) {
PrintUtils.displayReceivers(leftReceivers, rightReceivers, "");
PrintUtils.displayActions(originalleft, move2left, originalright, move2right);
MoveAction moveAction = new MoveAction();
moveAction.setMove2Left(move2left);
moveAction.setMove2Right(move2right);
moveActions.add(moveAction);
}
}
}
}
