消防员在车辆座椅上就座的算法

Question

我正在做一个项目，当志愿者消防员到达消防局取卡车时，让他们坐在座位上。

此外，一些消防员有驾照，一些人没有，还有一些人受过组长教育。

因此，我的想法是通过GPS跟踪他们，并向服务器发送到消防站的整数距离以及每个消防站的教育类型。

然后，每隔5秒运行一次算法，并根据新的GPS坐标改变自己的座位，直到1个人接近车站，然后标记为坐人。

这应该发生，直到没有空座位或不再有消防员呼叫或所有呼叫的消防员到达

我想要帮助的棘手的事情(除了如果我的想法是最优的)，就是让消防员的位置最优。

我在考虑做一个可能的角色的优先列表。以及一份必须离开车站的车辆的优先顺序列表。

然后选择优先级最高的车辆和最高优先级的角色，并用受过教育的最近的消防员填充它。

但是，如果他是一名车手，但已经设置了领队座位，只有1名车手来了，还有更多的领队来了，两辆车不得不离开，这将是一个错误的解决方案，因为第二辆车不能离开。

同样，如果司机而不是团队领导是最高优先级，那么如果最近的被设置为司机，但也是唯一具有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#？

这个问题让我很好奇。这是我所说的代码..eve如果你不用它的话

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));
            }
        }
    }
}