Few weeks back, I got a chance to work with a friend of mine on a Supply Chain problem. We wanted to develop and code an algorithm to produce an optimal solution. Before discussing the details of the solution, lets explore the problem first.
Problem
We have a graph of nodes. One of these nodes is the origin. We will call it 'source'. The source maintains a repository of goods to be delivered to other nodes in the graph. To deliver goods, we have a delivery truck which can carry a certain quantity of goods. We call it the truck capacity Ct. The delivery truck needs to visit each node and deliver the required quantity of goods. The required quanity of goods may or may not be different for each node. If the total requirement in the entire graph is, lets say 1000 units and the capacity of the truck is 100 units, the truck will deliver goods to nodes until its capacity is exhausted. It will then come back to the source for loading and will then resume visiting the left-out nodes. The whole process will continue until the truck serves all nodes in the graph.
We want to identify the optimal solution for this problem so that:
1. All nodes are served, keeping the requirement constraint of each node and the capacity of the truck
2. Best routes are identified with minimal distances to save travel time and expense
Solution
We initially targetted to solve the problem by using Tabu algorithm. However, we then decided to use 'clustering'. Clustering majorly implies grouping together similar items into groups or clusters. The similarity criterion may depend on the type of data. In most cases, the similarity criterion is least distant. In our problem, we cannot rely on least distance only. We not only need to make sure that routes/regions with least distance (between contained nodes) are identified but also the capacity constraint is not compromised. Therefore, we will cluster nodes on two criteria:
1. Clusters/Regions/Routes formed by nodes have the least distance/length
2. The total requirement of a cluster does not exceed the loading capacity of the truck
So, our solution works like this:
1. Load truck with goods.
2. Pick out a region and serve all nodes within that region.
3. Come back to source for reloading.
4. Repeat steps 1 to 3 until all regions are served
5. Come back to source
We devise the following algorithm to solve the problem.
Algorithm
1. Read network information from file
2. Calculate number of regions which can serve the whole network
3. Randomly assign nodes to regions such that the capacity of region is less than the capacity of truck
4. For each region, shuffle nodes within a region and get the best possible route with minimum length
5. Treat it as a possible solution
6. Run steps 2 to 4 for the given number of iterations
7. If the total length of all regions in this iteration is less than previous optimal solution, make it optimal solution
8. End with the optimal solution achieved
Source Code
using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace RoutingAlgo
{
public partial class Form1 : Form
{
private int[,] Nodes = new int[5000, 4];
private int NodesCount = 0;
int TotalCapacity = 0;
private ArrayList Regions = new ArrayList();
int RegionsCount = 0;
private double BestDistance = double.MaxValue;
private string BestRoute = String.Empty;
public Form1()
{
InitializeComponent();
GetCaseData();
}
private void Form1_Load(object sender, EventArgs e)
{
}
private int GetCaseData()
{ // Read network info from file
FileStream fs = null;
StreamReader Reader = null;
int status = 0;
try
{
fs = new FileStream(@"c:\CaseData.txt", FileMode.Open, FileAccess.Read);
Reader = new StreamReader(fs);
string SingleNode = String.Empty;
while ((SingleNode = Reader.ReadLine()) != null)
{ // read file line by line
//split each line with comma as delimiter and populate arrays
string[] NodeDetails = SingleNode.Split(',');
Nodes[NodesCount, 0] = int.Parse(NodeDetails[0]);
Nodes[NodesCount, 1] = int.Parse(NodeDetails[1]);
Nodes[NodesCount, 2] = int.Parse(NodeDetails[2]);
Nodes[NodesCount, 3] = int.Parse(NodeDetails[3]);
// Find total capacity required in the network
TotalCapacity = TotalCapacity + Nodes[NodesCount, 3];
lstNodes.Items.Add(SingleNode);
NodesCount++;
}
}
catch(Exception exc)
{
status = 1;
}
finally
{
if (Reader != null)
Reader.Close();
if (fs != null)
fs.Close();
}
return status;
}
private int GetRegionsCount()
{ // calculate number of regions required to serve the network
try
{ // divide total network capacity divided by truck capacity, round up answer
int Capacity = int.Parse(txtCapacity.Text);
if (TotalCapacity % Capacity == 0)
return TotalCapacity / Capacity;
else
return (TotalCapacity / Capacity) + 1;
}
catch (Exception exc)
{
return 0;
}
}
private int InitializeRegions()
{ // initialize regions array
RegionsCount = GetRegionsCount();
for (int i = 0; i < RegionsCount; i++)
{ // initialize array for each region
ArrayList ThisRegion = new ArrayList();
ThisRegion.Add(0); // first element will store the capacity of the region
ThisRegion.Add(Nodes[0, 0]); // origion will be the second node in every region
Regions.Add(ThisRegion);
}
return 0;
}
private int AssignNodesToRegions()
{ // randomly assign nodes to regions
Random Generator = new Random();
for (int i = 1; i < NodesCount; i++)
{ // for each node, assign randomly using random number generator
while (true)
{
ArrayList ThisRegion = (ArrayList)Regions[Generator.Next(RegionsCount)];
if (((int)ThisRegion[0] + Nodes[i, 3]) <= int.Parse(txtCapacity.Text))
{
ThisRegion[0] = (int)ThisRegion[0] + Nodes[i, 3];
ThisRegion.Add(Nodes[i, 0]);
break;
}
}
}
return 0;
}
private int DisplayResults()
{ // displays result in Results text box
txtRegions.Text = txtRegions.Text + "------------------" + "\n";
for (int i=0; i<RegionsCount; i++)
{
ArrayList ThisRegion = (ArrayList)Regions[i];
for (int j=0; j<ThisRegion.Count; j++)
{
txtRegions.Text = txtRegions.Text + ThisRegion[j] + "|";
}
txtRegions.Text = txtRegions.Text + " [" + GetRegionLength(ThisRegion) + "]\n";
}
return 0;
}
private ArrayList GetAlternativeRoute(ArrayList OriginalRegion, int Idx1, int Idx2)
{ // give a route, generate a new route by swapping two nodes within a region
ArrayList TempNode = new ArrayList(OriginalRegion);
// swapping two nodes within a region
int temp = (int)OriginalRegion[Idx1];
OriginalRegion[Idx1] = OriginalRegion[Idx2];
OriginalRegion[Idx2] = temp;
return TempNode;
}
private int ShuffleNodesInRegion()
{ // try all combinations of nodes within a region to acquire least distance
for (int k=0; k<RegionsCount; k++)
{
ArrayList ThisRegion = (ArrayList)Regions[k];
for (int i=2; i<ThisRegion.Count-1; i++)
{
for (int j=i+1; j<ThisRegion.Count; j++)
{ // swap every two nodes
ArrayList AlternateRoute = GetAlternativeRoute(ThisRegion, i, j);
if (GetRegionLength(AlternateRoute) < GetRegionLength(ThisRegion))
{ // if new route is better, make it permanent
ThisRegion.Clear();
Regions.RemoveAt(k);
Regions.Insert(k, AlternateRoute);
ThisRegion = (ArrayList)Regions[k];
}
}
}
}
return 0;
}
private int CheckBestRoute()
{ // for each set of regions calculated, see if this iteration produced an optimal solution
double Distance = 0;
for (int k = 0; k < RegionsCount; k++)
{
ArrayList ThisRegion = (ArrayList)Regions[k];
Distance = Distance + GetRegionLength(ThisRegion);
}
if (Distance < BestDistance)
{ // this solution is better than previous optimal solution
BestDistance = Distance;
BestRoute = String.Empty;
for (int i = 0; i < RegionsCount; i++)
{
ArrayList ThisRegion = (ArrayList)Regions[i];
BestRoute = BestRoute + "[" + ThisRegion[0] + "]";
for (int j = 1; j < ThisRegion.Count; j++)
{
BestRoute = BestRoute + ThisRegion[j] + "|";
}
BestRoute = BestRoute + "\n";
}
}
return 0;
}
private void btnRun_Click(object sender, EventArgs e)
{ // run routing algorithm
try
{
for (int i = 0; i < int.Parse(txtIterations.Text); i++)
{
InitializeRegions();
AssignNodesToRegions();
ShuffleNodesInRegion();
DisplayResults();
CheckBestRoute();
Regions.Clear();
}
txtRegions.Text = txtRegions.Text + "\nBest Route\n----------\n" + BestRoute;
txtRegions.Text = txtRegions.Text + "\nBest Distance\n----------\n" + BestDistance.ToString();
}
catch (Exception exc)
{
txtRegions.Text = exc.ToString();
}
}
private double GetRegionLength(ArrayList ThisRegion)
{ // calculate length of a region
double RegionDistance = 0;
for (int i=1; i<ThisRegion.Count-1; i++)
{ // add distances of subsequent nodes
Point P1 = new Point(Nodes[(int)ThisRegion[i], 1], Nodes[(int)ThisRegion[i], 2]);
Point P2 = new Point(Nodes[(int)ThisRegion[i+1], 1], Nodes[(int)ThisRegion[i+1], 2]);
RegionDistance = RegionDistance + CalculateEuclideanDistance(P1, P2);
}
// add distance of first node to last node as truck will need to go back to the origin
Point P0 = new Point(Nodes[(int)ThisRegion[0], 1], Nodes[(int)ThisRegion[0], 2]);
Point Pn = new Point(Nodes[(int)ThisRegion[ThisRegion.Count - 1], 1], Nodes[(int)ThisRegion[ThisRegion.Count - 1], 2]);
RegionDistance = RegionDistance + CalculateEuclideanDistance(P0, Pn);
return RegionDistance;
}
private double CalculateEuclideanDistance(Point A, Point B)
{ // return euclidean distance between two points in graph
return Math.Sqrt(Math.Pow(A.X - B.X, 2) + Math.Pow(A.Y - B.Y, 2));
}
}
}Graph Representation
We will take graph information as an input file. The following is a sample file:
0,82,76,0
1,96,44,19
2,50,5,21
3,49,8,6
4,13,7,19
5,29,89,7
6,58,30,12
7,84,39,16
8,14,24,6
9,2,39,16
10,3,82,8
11,5,10,14
12,98,52,21
13,84,25,16
14,61,59,3
15,1,65,22
16,88,51,18
17,91,2,19
18,19,32,1
19,93,3,24
20,50,93,8
21,98,14,12
22,5,42,4
23,42,9,8
24,61,62,24
25,9,97,24
26,80,55,2
27,57,69,20
28,23,15,15
29,20,70,2
30,85,60,14
31,98,5,9
Each line represents a node. The first node is the source. The first component in a node represents node identifier, the second and third are X and Y co-ordinates respectively, and the last component is goods requirement for the node.
Results
The following is the screenshot of the user interface:
The higher the number of iterations, the better the solution. For 20 iterations, we got the solution in 2 secs. For 100 iterations, we got the solution in 10 secs with a significant improvement in distance.
For 200 iterations, the program took 31 secs and produced a better result. However, we notice that as we increase the number of iterations further, the execution time is increasing rapidly while we do not see drastic improvement in solution.
Therefore, we can conclude that 200 is a good number of iterations to get optimal solution.
Conclusion
The program succeeds to provide good results in reasonable time. However, an improvement in data structrues can reduce the execution time of the program. Moreover, the algorithm still has room for improvement. We may do these modifications in future, but for now we are pretty happy with the results.
Cheers!
JS
No comments:
Post a Comment