运输算法

计算科学 算法
2021-12-24 17:57:19

我最初将其发布在数学 StackExchange 中,但有人告诉我这更像是一个运筹学问题。我想知道是否有人对如何寻找答案有任何想法。

我有以下场景,我想找到一种算法以便将其放入 ac# 程序:Transportation Inc 签订合同,将 2 吨板条箱从站点 A 运送到站点 B,他们希望找到最有效的方式来做到这一点以下约束:

  • 所有 4 辆卡车最初都在站点 B。

  • 无论行驶方向如何,一次只能有 2 辆卡车上路。

  • 每辆卡车最多可装载 6 个板条箱

  • 从一个站点到另一个站点需要 30 分钟

  • 将板条箱放在卡车上需要 5 分钟,从卡车上取下板条箱需要 5 分钟

需要提供一种算法才能在 6 小时内运输最多的箱子。

我想我可能必须用 c# 编写一个模拟,但我想知道其他人对如何为这个问题编写更有效的算法的想法。

了解了算法,然后可以使不同的变量变得灵活,以便他们可以测试看看增加更多卡车或更有效的装卸会对结果产生什么影响。

谢谢

1个回答

这是我想出的解决方案。我写了一个卡车模拟。但我愿意接受更好的解决方案

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Infrastructure
{
    public enum TruckState
    {
        Loading,
        Unloading,
        TravalingToPickupSite,
        TravelingToDropOffSite,
        WaitingToLeavePickupSite,
        WaitingToLeaveDropOffSite,
        WaitingToBeLoaded,
        WaitingToBeUnloaded
    }

    public class MainStart
    {
        static void Main()
        {
            var truckSimulation = new TruckSimulation();
            var result = truckSimulation.RunSimulation();
            Console.WriteLine("Crates delivered: " + result);
            Console.WriteLine("Press any key to exit.");
            Console.ReadKey();
        }
    }

    public class TruckSimulation
    {
        public const int MaxLoad = 6;
        public const int TimeToUnloadACrate = 5;
        public const int TimeToLoadACrate = 5;
        public const int TimeToPickUpSite = 30;
        public const int TimeToDropOffSite = 30;
        public const int TotalTime = 360;
        public const int TotalTrucks = 6;
        public const int MaxTrucksOnRoad = 6;

        public TruckSimulation()
        {
            Trucks = new List<Truck>();
            for (int i = 0; i < TotalTrucks; i++)
            {
                var Truck = new Truck();
                Truck.LoadCount = 0;
                Truck.CurrentTruckState = TruckState.WaitingToLeaveDropOffSite;
                Truck.TimeToNextTruckState = 0;
                Trucks.Add(Truck);
            }
            CurrentTime = 0;
            TotalCratesDroppedOff = 0;
        }


        public List<Truck> Trucks { get; set; }
        public int TotalCratesDroppedOff { get; set; }
        public int CurrentTime { get; set; }
        public int TrucksOnTheRoad { get; set; }

        public int RunSimulation()
        {
            // start time
            do
            {
                TruckWaitingToBeLoaded();
                TruckLoading();
                TruckWaitingToLeavePickupSite();
                TruckTravelingToDropOffSite();
                TruckWaitingToBeUnloaded();
                TruckUnloading();
                TruckWaitingToLeaveDropOffSite();
                TruckTravalingToPickupSite();  

                // increment time
                CurrentTime++;
            } while (CurrentTime <= TotalTime);

            return TotalCratesDroppedOff;
        }

        public void TruckWaitingToBeLoaded()
        {
            // look for Truck waiting to be loaded and change to start loading and change TruckState and set time to next TruckState
            var TruckWaitingtoBeLoaded = FindFirstTruckWithTruckState(TruckState.WaitingToBeLoaded);
            if (TruckWaitingtoBeLoaded != null && FindFirstTruckWithTruckState(TruckState.Loading) == null)
            {
                TruckWaitingtoBeLoaded.CurrentTruckState = TruckState.Loading;
                TruckWaitingtoBeLoaded.TimeToNextTruckState = CurrentTime + TimeToLoadACrate;
            }
        }

        public void TruckLoading()
        {
            // look for Truck that is loading and check if ready for next Crate
            var TruckThatIsLoading = FindFirstTruckWithTruckState(TruckState.Loading);
            if (TruckThatIsLoading != null)
            {
                if (TruckThatIsLoading.TimeToNextTruckState == CurrentTime)
                {
                    TruckThatIsLoading.LoadCount++;
                    if (TruckThatIsLoading.LoadCount < MaxLoad)
                    {
                        TruckThatIsLoading.TimeToNextTruckState = CurrentTime + TimeToLoadACrate;
                    }
                    else
                    {
                        TruckThatIsLoading.CurrentTruckState = TruckState.WaitingToLeavePickupSite;
                    }
                }
            }
        }

        public void TruckWaitingToLeavePickupSite()
        {
            // look for Truck that is waiting to leave pick up site, check to see if can send to drop off site (if less than two Trucks on the Road)
            var TruckWaitingToLeavePickupSite = FindFirstTruckWithTruckState(TruckState.WaitingToLeavePickupSite);
            if (TruckWaitingToLeavePickupSite != null)
            {
                if (TrucksOnTheRoad < MaxTrucksOnRoad)
                {
                    TruckWaitingToLeavePickupSite.CurrentTruckState = TruckState.TravelingToDropOffSite;
                    TruckWaitingToLeavePickupSite.TimeToNextTruckState = CurrentTime + TimeToDropOffSite;
                    TrucksOnTheRoad++;
                }
            }
        }

        public void TruckTravelingToDropOffSite()
        {
            // look for Truck that is on the Road and if ready to unload
            foreach (var TruckTravelingToDropOffSite in FindAllTrucksWithTruckState(TruckState.TravelingToDropOffSite))
            {
                if (TruckTravelingToDropOffSite != null)
                {
                    if (TruckTravelingToDropOffSite.TimeToNextTruckState == CurrentTime)
                    {
                        TruckTravelingToDropOffSite.CurrentTruckState = TruckState.WaitingToBeUnloaded;
                        TrucksOnTheRoad--;
                    }
                }
            }
        }

        public void TruckWaitingToBeUnloaded()
        {
            // look for Truck that is waiting to be unloaded
            var TruckWaitingToBeUnloaded = FindFirstTruckWithTruckState(TruckState.WaitingToBeUnloaded);
            if (TruckWaitingToBeUnloaded != null && FindFirstTruckWithTruckState(TruckState.Unloading) == null)
            {
                TruckWaitingToBeUnloaded.CurrentTruckState = TruckState.Unloading;
                TruckWaitingToBeUnloaded.TimeToNextTruckState = CurrentTime + TimeToUnloadACrate;
            }
        }

        public void TruckUnloading()
        {
            // look for Truck that is unloading and is ready to unload another Crate
            var TruckThatIsUnloading = FindFirstTruckWithTruckState(TruckState.Unloading);
            if (TruckThatIsUnloading != null)
            {
                if (TruckThatIsUnloading.TimeToNextTruckState == CurrentTime)
                {
                    TruckThatIsUnloading.LoadCount--;
                    TotalCratesDroppedOff++;
                    if (TruckThatIsUnloading.LoadCount == 0)
                    {
                        TruckThatIsUnloading.CurrentTruckState = TruckState.WaitingToLeaveDropOffSite;
                    }
                    else
                    {
                        TruckThatIsUnloading.TimeToNextTruckState = CurrentTime + TimeToUnloadACrate;
                    }
                }
            }
        }

        public void TruckWaitingToLeaveDropOffSite()
        {
            // look for a Truck that is waiting to leave drop off site
            var TruckWaitingToLeaveDropOffSite = FindFirstTruckWithTruckState(TruckState.WaitingToLeaveDropOffSite);
            if (TruckWaitingToLeaveDropOffSite != null)
            {
                if (TrucksOnTheRoad < MaxTrucksOnRoad)
                {
                    TruckWaitingToLeaveDropOffSite.CurrentTruckState = TruckState.TravalingToPickupSite;
                    TruckWaitingToLeaveDropOffSite.TimeToNextTruckState = CurrentTime + TimeToPickUpSite;
                    TrucksOnTheRoad++;
                }
            }
        }

        public void TruckTravalingToPickupSite()
        {
            // look for a Truck that has arrived at the pickup site
            foreach (var TruckTravelingToPickupSite in FindAllTrucksWithTruckState(TruckState.TravalingToPickupSite))
            {
                if (TruckTravelingToPickupSite != null)
                {
                    if (TruckTravelingToPickupSite.TimeToNextTruckState == CurrentTime)
                    {
                        TrucksOnTheRoad--;
                        TruckTravelingToPickupSite.CurrentTruckState = TruckState.WaitingToBeLoaded;
                    }
                }
            }
        }

        public Truck FindFirstTruckWithTruckState(TruckState TruckState)
        {
            return Trucks.FirstOrDefault(x => x.CurrentTruckState == TruckState);
        }

        public List<Truck> FindAllTrucksWithTruckState(TruckState TruckState)
        {
            return Trucks.Where(x => x.CurrentTruckState == TruckState).ToList();
        }
    }

    public class Truck
    {
        public Truck()
        {
            LoadCount = 0;
            CurrentTruckState = TruckState.WaitingToLeaveDropOffSite;
            TimeToNextTruckState = 0;
        }
        public int LoadCount { get; set; }
        public TruckState CurrentTruckState { get; set; }
        public int TimeToNextTruckState { get; set; }
    }
}