用於在車輛座椅上安裝消防員的算法

Question

我正在做一個項目，該項目涉及將志願消防員安排在座位上，當他們到達消防站時拿走卡車。

另外一些消防員有駕駛執照一些沒有和一些有團隊領導的教育。

所以我的想法是通過GPS跟蹤他們，並向服務器發送消防站的整數距離以及每種教育類型。

然後每隔5秒運行一次算法，並根據新的GPS座標改變座位，直到1靠近車站，然後標記爲坐位。

這應該發生，直到沒有空座位或不再消防人員調用或全稱爲消防隊員已經趕到

我想幫助棘手的事情（除了如果我的想法是最佳），是座位消防員最優化。

我正在考慮制定一個可能的角色的優先級列表。 還有一個需要離開車站的車輛優先列表。

然後選擇最高優先級的車輛和最高優先級的角色，並填寫與最接近教育的消防隊員。但是如果他是一名車手，但已經設置爲車隊領導席位，並且只有1名車手來了，而且還有更多車隊領隊前來，並且兩輛車不得不離開，那麼這將是一個錯誤的解決方案，因爲第二名車手不得不離開車輛不能離開。

此外，如果司機和不是teamleaders是最高優先級，那麼如果最接近的設置爲司機，但也是唯一一個與teamleader教育，但更多的司機來了，那也將是錯誤的。

算法的任何想法工作？還是有人知道這個算法？

Answer 1

你是對的，這種貪婪的方法不一定會給你一個最佳的解決方案。你看過/聽說過線性規劃或更具體的整數規劃：http://en.wikipedia.org/wiki/Integer_programming

簡而言之整數規劃是解決這些類型的調度問題的一種技術。這個問題有一些你希望最大化或最小化的目標，並受到各種（線性）限制。整數因爲我們不能有一半的志願者。

從您的描述中，目標函數可能是最小化未拆卸卡車的數量和總等待時間。不同的卡車可以爲不同的成本獲取不同的車輛優先級。

限制條件包括每輛車至少需要一名駕駛員，至少一名車隊負責人以及一名志願者只能分配到一輛車。可能還有其他的限制你沒有描述，比如沒有人可以在基地等待超過20分鐘。

如果您搜索整數編程和調度，您應該找到一些代碼示例。你可能需要一個求解器來協助。維基有一個相當全面的名單，選擇將歸結爲您的編程語言偏好和預算：http://en.wikipedia.org/wiki/Linear_programming#Solvers_and_scripting_.28programming.29_languages

Answer 2

這樣的事情如何.. 正如你注意到的唯一相互衝突的情況是，當你有一個消防員，可以是司機和領導..因爲只能佔據一個位置..但可能會阻止另一個..

所以不要開始與他們。首先開始與具有醚潛水員的那些執照或領導教育..因爲那些已經預定座位（他們可以採取的唯一）..之後那些充滿

..指派那些可以做乙醚工作，對於丟失或更換一些，如果他們是接近的席位。

在擁有一列駕駛員隊伍和一隊領隊之後，按照距離消防站的距離對其進行排序，然後分配給卡車成對......然後填滿剩下的卡車......通過ETA命令從隊列中移除。 。

不知道它總會給最好的解決辦法..但是你想一些代碼看起來相當最佳..什麼？ C＃？

的問題讓我很好奇這樣。這裏是我在說什麼..前夕，如果你不使用它

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 

namespace FF 
{ 
    class Program 
    { 
     [Flags] 
     public enum Skill 
     { 
      None = 0, 
      Driver = 1, 
      TeamLeader = 2, 
     } 
     public class FireFighter : IComparable<FireFighter> 
     { 
      public int ID; 
      public Skill Skills;//the skills that he has 
      public Skill Assigned;//the one that he will be deployed with 
      public int ETA; 
      public override string ToString() 
      { 
       return ID + "(" + Skills + ")" + " @ " + ETA + " minutes as " + this.Assigned; 
      } 


      int IComparable<FireFighter>.CompareTo(FireFighter other) 
      { 
       return this.ETA.CompareTo(other.ETA); 
      } 
     } 
     public class Truck 
     { 
      public int ID; 
      public int Capacity; 
      public List<FireFighter> Crew = new List<FireFighter>(); 
     } 
     static int TotalStationTrucks = 8; 
     static List<Truck> Trucks = new List<Truck>(); 
     static List<FireFighter> Team = new List<FireFighter>(); 
     static Random Rnd = new Random(); 
     static void Main(string[] args) 
     { 
      //create the sample data 
      int nAvailableSeats = 0; 
      for (int i = 0; i < TotalStationTrucks; i++) 
      { 
       Truck oTruck = new Truck(); 
       oTruck.ID = i; 
       nAvailableSeats += oTruck.Capacity = Rnd.Next(4, 7);//seats between 4 - 6 
       Trucks.Add(oTruck); 
      } 
      for (int i = 0; i < nAvailableSeats * 2; i++)//add twice the amount of FF we need for all trucks 
      { 
       FireFighter oFireFighter = new FireFighter(); 
       oFireFighter.ID = i; 
       oFireFighter.ETA = Rnd.Next(Int16.MaxValue); 
       Team.Add(oFireFighter); 
      } 
      for (int i = 0; i < Trucks.Count * 2; i++)//add twice the drivers we need 
      { 
       FireFighter oFireFighter = Team[Rnd.Next(Team.Count)]; 
       oFireFighter.Skills |= Skill.Driver; 
      } 
      for (int i = 0; i < Trucks.Count * 2; i++)//add twice the leaders we need 
      { 
       FireFighter oFireFighter = Team[Rnd.Next(Team.Count)]; 
       oFireFighter.Skills |= Skill.TeamLeader; 
      } 
      for (int i = 0; i < Trucks.Count * 2; i++)//add twice the multitaskers we need 
      { 
       FireFighter oFireFighter = Team[Rnd.Next(Team.Count)]; 
       oFireFighter.Skills = (Skill.TeamLeader|Skill.Driver); 
      } 
      //Truck that are going to be deployed 
      int nTrucksToDeploy = Rnd.Next(2, Trucks.Count); 

      // distribute firefighter by ETA to minimize truck deploy 
      //******************************************************* 

      //Sort by ETA 
      Team.Sort(); 
      //get top the ones that can only drive 
      List<FireFighter> oSelectedDrivers = Team.FindAll(delegate(FireFighter item) { return item.Skills == Skill.Driver; }).GetRange(0, nTrucksToDeploy); 
      oSelectedDrivers.ForEach(delegate(FireFighter item) { item.Assigned = Skill.Driver; }); 

      //get top the ones that can only lead 
      List<FireFighter> oSelectedLeaders = Team.FindAll(delegate(FireFighter item) { return item.Skills == Skill.TeamLeader; }).GetRange(0, nTrucksToDeploy); 
      oSelectedLeaders.ForEach(delegate(FireFighter item) { item.Assigned = Skill.TeamLeader; }); 

      //put them on a list of already assigned 
      List<FireFighter> oAssigned = new List<FireFighter>(); 
      oAssigned.AddRange(oSelectedDrivers); 
      oAssigned.AddRange(oSelectedLeaders); 

      //get the ones that can do ether job 
      List<FireFighter> oMultitaskers = Team.FindAll(delegate(FireFighter item) { return item.Skills == (Skill.Driver | Skill.TeamLeader); }); 
      //sort by ETA 
      oMultitaskers.Sort(); 
      oAssigned.Sort(); 
      //put a multitaskers in the queue if he is gonna arrive earlier than the most delayed 
      while (oMultitaskers[0].ETA < oAssigned[oAssigned.Count - 1].ETA) 
      { 
       FireFighter oIsOut = oAssigned[oAssigned.Count - 1]; 
       FireFighter oIsIn = oMultitaskers[0]; 
       //swap tasks 
       oIsIn.Assigned = oIsOut.Assigned; 
       oIsOut.Assigned = Skill.None; 
       //remove from respective queues 
       oAssigned.RemoveAt(oAssigned.Count - 1); 
       oMultitaskers.RemoveAt(0); 
       //Add the multitasker to queue 
       //and if you are questioning if the could get a better solution by choosing another assignment 
       //that as no influence.. the optmizing condition is removing the slowest that was on queue 
       oAssigned.Add(oIsIn); 
       //the out guy is not added for two reasons 
       //1st is not a multitasker 
       //2nd and most importante.. he was the one with the highest ETA, we will NEVER gain by replacing another driver with this one 
       //oMultitaskers.Add(oIsOut); 

       oMultitaskers.Sort(); 
       oAssigned.Sort(); 
      } 

      //start filling the trucks take one of each from top, wich means the first truck will have the earliest departure 
      for (int i = 0; i < nTrucksToDeploy; i++) 
      { 
       int nDriverIndex = oAssigned.FindIndex(delegate(FireFighter item) { return item.Assigned == Skill.Driver; }); 
       Trucks[i].Crew.Add(oAssigned[nDriverIndex]); 
       oAssigned.RemoveAt(nDriverIndex); 
       int nLeaderIndex = oAssigned.FindIndex(delegate(FireFighter item) { return item.Assigned == Skill.TeamLeader; }); 
       Trucks[i].Crew.Add(oAssigned[nLeaderIndex]); 
       oAssigned.RemoveAt(nLeaderIndex); 
      } 
      //now fill the rest of the crew.. also ordered by ETA 
      List<FireFighter> oUnassigned = Team.FindAll(delegate(FireFighter item) { return item.Assigned == Skill.None; }); 
      oUnassigned.Sort(); 
      for (int i = 0; i < nTrucksToDeploy; i++) 
      { 
       while (Trucks[i].Crew.Count < Trucks[i].Capacity) 
       { 
        Trucks[i].Crew.Add(oUnassigned[0]); 
        oUnassigned.RemoveAt(0); 
       } 
      } 

      //dump truck data 
      Trace.WriteLine(String.Format("{0} trucks to be deployed",nTrucksToDeploy)); 
      for (int i = 0; i < nTrucksToDeploy; i++) 
      { 
       Trace.WriteLine(new String('-', 20)); 
       Truck oTruck = Trucks[i]; 
       oTruck.Crew.Sort(); 
       Trace.WriteLine(String.Format("truck {0} estimated time of departure: {1}",oTruck.ID,oTruck.Crew[oTruck.Crew.Count-1].ETA)); 
       for (int j = 0; j < oTruck.Crew.Count; j++) 
       { 
        FireFighter oFireFighter = oTruck.Crew[j]; 
        Trace.WriteLine(String.Format("{0}({1})\t @ {2} minutes as \t{3}", oFireFighter.ID, oFireFighter.Skills, oFireFighter.ETA, oFireFighter.Assigned)); 
       } 

      } 
      Trace.WriteLine(new String('#', 20)); 
      //list the team 
      for (int i = 0; i < Team.Count; i++) 
      { 
       FireFighter oFireFighter = Team[i]; 
       Trace.WriteLine(String.Format("{0}({1})\t @ {2} minutes as \t{3}", oFireFighter.ID, oFireFighter.Skills, oFireFighter.ETA, oFireFighter.Assigned)); 
      } 
     } 
    } 
}