4
$\begingroup$

I originally posted this in the mathematics StackExchange, but I was told that this is more of an operations research question. I would like to know if anyone has any thoughts on how to go about finding an answer.

I have the following scenario that I want to find an algorithm for in order to put into a c# program: Transportation Inc is contracted to ship 2 ton crates from site A to site B and they want to find the most efficient way to do so with the following constraints:

  • All 4 trucks are initially at site B.

  • Only 2 trucks can be on the road at a time, regardless of the direction of travel.

  • Each truck can carry no more than 6 crates

  • Going from one site to another takes 30 minutes

  • Putting a crate on a truck takes 5 minutes, and removing a crate from a truck takes 5 minutes

An algorithm needs to be provided in order to transport the most crates for a 6 hour period.

I thought I might have to write up a simulation in c#, but I would like to know other people's thoughts on how to write a more efficient algorithm for this problem.

Knowing the algorithm, then different variables could be made flexible so that they could test to see what adding more trucks or more efficient loading and unloading would have on the result.

Thanks

$\endgroup$
  • $\begingroup$ If you can formulate it as a linear program (which you likely can), then the simplex algorithm would provide a globally optimal solution. On a problem of this size, it would likely do so very quickly as well. $\endgroup$ – Godric Seer Sep 27 '13 at 20:05
  • $\begingroup$ Can the crates be loaded/unloaded in parallel? By that I mean can you load 2 crates onto truck one at the same time OR can you load one crate onto two trucks at the same time? $\endgroup$ – Daryl Sep 27 '13 at 20:39
  • $\begingroup$ I believe there is only one crate loading team, so one crate on one truck at a time. $\endgroup$ – user1408767 Sep 27 '13 at 23:36
  • $\begingroup$ This is a typical scheduling problem for which there is a huge amount of literature. These problems are typically formulates as linear programs with linear constraints, and then thrown into LP solvers. $\endgroup$ – Wolfgang Bangerth Sep 28 '13 at 2:23
2
$\begingroup$

Here is a solution I came up with. I wrote a truck simulation. But I am open to better solutions

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; }
    }
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.