# Shipping algorithm

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.

Thanks

• 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. Sep 27, 2013 at 20:05
• 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? Sep 27, 2013 at 20:39
• I believe there is only one crate loading team, so one crate on one truck at a time. Sep 27, 2013 at 23:36
• 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. Sep 28, 2013 at 2:23

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
{
TravalingToPickupSite,
TravelingToDropOffSite,
WaitingToLeavePickupSite,
WaitingToLeaveDropOffSite,
}

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

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.CurrentTruckState = TruckState.WaitingToLeaveDropOffSite;
Truck.TimeToNextTruckState = 0;
}
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
{
TruckWaitingToLeavePickupSite();
TruckTravelingToDropOffSite();
TruckWaitingToLeaveDropOffSite();
TruckTravalingToPickupSite();

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

}

{
// look for Truck waiting to be loaded and change to start loading and change TruckState and set time to next TruckState
{
}
}

{
{
{
{
}
else
{
}
}
}
}

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)
{
{
TruckWaitingToLeavePickupSite.CurrentTruckState = TruckState.TravelingToDropOffSite;
TruckWaitingToLeavePickupSite.TimeToNextTruckState = CurrentTime + TimeToDropOffSite;
}
}
}

public void TruckTravelingToDropOffSite()
{
foreach (var TruckTravelingToDropOffSite in FindAllTrucksWithTruckState(TruckState.TravelingToDropOffSite))
{
if (TruckTravelingToDropOffSite != null)
{
if (TruckTravelingToDropOffSite.TimeToNextTruckState == CurrentTime)
{
}
}
}
}

{
// look for Truck that is waiting to be unloaded
{
}
}

{
{
{
TotalCratesDroppedOff++;
{
}
else
{
}
}
}
}

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

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

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()
{