Tutorials‎ > ‎

Solving Route Problem using Savings Algorithm Implemented with C# and OpenTK

posted Dec 23, 2014, 2:35 AM by Sujono _   [ updated Aug 15, 2016, 11:37 PM by Surya Wang ]

Hello, welcome to my tutorial. In this tutorial, we will learn about savings algorithm and how to implemented it in C# and OpenTK. Let's begin with the description about savings algorithm first.

A. Savings Algorithm
    
Clarke & Wright Savings algorithm is the method found by Clarke and Wright in 1964. This method is published as the algorithm used to find the solution of route problem. The work of this method is to exchange some routes at each step so we get the optimized route result. The process is not only calculate the distance, but also the biggest savings value obtained from the mileage between source and destination node. 
   Savings algorithm has 2 goal, which are
   a. Minimalized total mileage of all vehicle directly.
   b. Minimalized the number of vehicles that are necessary for serving all customer indirectly.

   Here are the following steps of Savings algorithm:
   1. Calculate Savings value with this equation for each node:
    s(i, j) = d (D, i) + d (D, j) – d (i, j)
    where:
    i : row
    j : column
   2. Create the rank system of Savings value ordered by ascending.
   3. Allocate node to route, then
   4. Sort target in route that has been defined.

B. OpenTK
    
OpenTK (Open Toolkit) is a C# library consists of OpenGL, OpenCL, dan OpenAL. OpenTK is developed exclusively for C# language because of these reasons, which are:
a. Fast.
b. Easy to use.
No leak memory
No need header files
Easier to read
c. Inter-Platform Distribution with Mono

C. Pre-code :

For this apps, we need to store the data consists of: Node, Distance, and Saving (Optional). I have attached them in this tutorial, so you can use it in your program by using MySQL or SQL Server connection.

Here are the view of my data:

  • Node table.

  • Distance table.

  • Saving table (optional).

 

D. Create The Program!

1. First, we create the savingRoute class used for two purposes, such as:
a. Save the saving cost and route.
b. Check the larger route.

Here's the code:

public class savingRoute
    {
        public float savingCost;
        public String Route;
        Connection con = new Connection();

        public savingRoute(float savingCost, String Route)
        {
            this.savingCost = savingCost;
            this.Route = Route;
        }

        public float cekLargerRoute(savingRoute sr, List<savingRoute> lsr)
        {
            foreach (var x in lsr)
            {
                if (sr.Route[2].Equals(x.Route[0]) && sr.Route[0].Equals(x.Route[2]))
                    return sr.savingCost >= x.savingCost ? sr.savingCost : x.savingCost;
            }
            return 0.0f;
        }
    }

2. Create the DistanceAndSaving Form with four data grid view tables and buttons as follows: 


Then, create the function for Savings process in DistanceAndSaving Form:

        private void SavingProcess_Click(object sender, EventArgs e)
        {
            //Membuat Tabel Saving
            DestinationSavingTable.Enabled = true;
            DataTable savingTable = new DataTable();
            DataColumn ij = new DataColumn("i-j");
            savingTable.Columns.Add(ij);
            for (int i = 1; i < dataGridView1.ColumnCount; i++)
                savingTable.Columns.Add(dataGridView1.Columns[i].Name);
            String asd = "";
            for (int i = 0; i < dataGridView1.Rows.Count; i++)
            {
                DataRow newRow = savingTable.NewRow();
                    newRow["i-j"] = dataGridView1.Rows[i].Cells[0].Value.ToString();
                for (int j = 1; j < savingTable.Columns.Count; j++)
                {
                    newRow[dataGridView1.Rows[j - 1].Cells[0].Value.ToString()] =
                    (j != 1) ?
                    i + 1 != j ?
                    (
                    float.Parse(dataGridView1.Rows[0].Cells[i + 1].Value.ToString()) +
                    float.Parse(dataGridView1.Rows[0].Cells[j].Value.ToString()) -
                    float.Parse(dataGridView1.Rows[i].Cells[j].Value.ToString())).ToString("0.00")
                    : "0"
                    : "0";
                }
                savingTable.Rows.Add(newRow);
            }

            dataGridView2.DataSource = savingTable;
        }

3. Create the function for destination Savings table refer to the input before:

 private void DestinationSavingTable_Click(object sender, EventArgs e)
        {
            //Membuat Tabel Saving Destination
            sorting.Enabled = true;
            DataTable nmSpbu = con.openDataTable("SELECT name From newsaving");
            for (int i = 0; i < nmSpbu.Rows.Count; i++)
            {
                arrange[i] = nmSpbu.Rows[i][0].ToString();
            }

            int index = 0;
            foreach (var x in arrange)
            {
                    index += choose.Where(a => a.Trim().Contains(x.Trim())).FirstOrDefault() != null ? 1 : 0;
                    selectColumn += choose.Where(a => a.Trim().Contains(x.Trim())).FirstOrDefault() != null ? (index != choose.Count ? x + "," : x + "") : "";
                    constraintColumn += choose.Where(a => a.Trim().Contains(x.Trim())).FirstOrDefault() != null ? (index != choose.Count ? "'" + x + "'," : "'" + x + "'") : "";
            }


            String queryRes = "SELECT name," + selectColumn + " FROM newsaving WHERE name IN(" + constraintColumn + ")";

            String ab = queryRes;
            int ac = index;
            DataTable result = con.openDataTable(queryRes);
            dataGridView3.DataSource = result;
        }

4. Sort the Destination saving table by Savings cost ascending:

public void getDataGridView()
        {
            //Sorting Tabel Saving Destination
            for (int rows = 0; rows < dataGridView3.Rows.Count; rows++)
            {
                for (int col = 1; col < dataGridView3.Rows[rows].Cells.Count; col++)
                {
                    sr.Add(new savingRoute(float.Parse(dataGridView3.Rows[rows].Cells[col].Value.ToString()), (rows + 1) + "," + (col)));
                }
            }
            sr = sr
                .Select(a => new savingRoute(a.savingCost = a.cekLargerRoute(a, sr), a.Route))
                .Where(a => Int32.Parse(a.Route[0] + "") >= Int32.Parse(a.Route[2] + ""))
                .OrderByDescending(a => a.savingCost).ToList();
            DataTable dt = new DataTable();
            DataColumn kn = new DataColumn("Koordinat Node");
            DataColumn savings = new DataColumn("Saving");
            dt.Columns.Add(kn);
            dt.Columns.Add(savings);

            foreach (var x in sr)
            {
                DataRow newRow = dt.NewRow();
                newRow["Koordinat Node"] = x.Route;
                newRow["Saving"] = x.savingCost;
                dt.Rows.Add(newRow);
            }
            dataGridView4.DataSource = dt;

        }

5. Create the OptimizedRoute Form with two data grid view tables, one button and GL control as follows (don't forget to add reference the OpenTK library in your project) : 



Then, build the OptimizedRoute Object that had been shipped the list of savingRoute, selected and constraint column.

  private void button1_Click(object sender, EventArgs e)
        {
            OptimizedRoute op = new OptimizedRoute(sr,selectColumn,constraintColumn);
            op.Show();
        }

Here's the preview of SavingAndDistance Form :




6. In this step, we have the coordinate (latitude,longitude) from each node. Because the coordinate value is between 0 - 180 degree, we must normalize the coordinate value from each node. Here is the formula:
latitude = (latitude - MinLatitude)  / (MaxLatitude - MinLatitude)
longitude = (longitude - MinLongitude)  / (MaxLongitude - MinLongitude)

Here's the constructor code when OptimizedRoute is created:

 
  public OptimizedRoute(List<savingRoute> sr, String selectColumn, String constraintColumn)
        {
            //Mengambil nama, latitude, dan longitude dari SPBU
            InitializeComponent();
            String queryRes = "SELECT name," + selectColumn + " FROM newsaving WHERE name IN(" + constraintColumn + ")";
            DataTable result = con.openDataTable(queryRes);
            dataGridView1.DataSource = result;
            this.sr = sr;
            queryRes = "SELECT name, latitude, longitude FROM node WHERE name ";
            String[] arrChoose = selectColumn.Split(',');
            foreach (var x in arrChoose)
            {
                queryRes += "LIKE '%" + x + "%' ";
                queryRes += x == arrChoose.LastOrDefault() ? "" : " OR name ";
            }
            queryRes += " OR name LIKE '%O%'";
            result = con.openDataTable(queryRes);
            for (int i = 0; i < result.Rows.Count; i++)
            {
                latChoose.Add(Double.Parse(result.Rows[i][1].ToString()));
                longChoose.Add(Double.Parse(result.Rows[i][2].ToString()));
                SaveChoose.Add(!result.Rows[i][0].ToString().ToLowerInvariant().Trim().Equals("O") ?
                result.Rows[i][0].ToString()
                : "O");
            }
            dataGridView2.DataSource = result;
            
            result = con.openDataTable("SELECT latitude, longitude FROM node");
            for (int i = 0; i < result.Rows.Count; i++)
            {
                latData.Add(Double.Parse(result.Rows[i][0].ToString()));
                longData.Add(Double.Parse(result.Rows[i][1].ToString()));
            }
            //Mengambil min/max dari latitude/longitude
            MinLat = latData.OrderBy(a => a).First();
            MaxLat = latData.OrderByDescending(a => a).First();
            MinLong = longData.OrderBy(a => a).First();
            MaxLong = longData.OrderByDescending(a => a).First();
            for (int i = 0; i < latChoose.Count; i++)
            {
                latChoose[i] = (latChoose[i] - MinLat) / (MaxLat - MinLat);
                longChoose[i] = (longChoose[i] - MinLong) / (MaxLong - MinLong);
            }
        }

7. Draw the cartesius diagram (horizontal and vertical line) with value between 0-1.

  void drawCartesian()
        {
            //Menggambar sumbu cartesius
            GL.LineWidth(1f);
            GL.Color3(0, 0, 0);
            GL.Begin(BeginMode.Lines);
            
            // vertical-tegak lurus
            GL.Vertex2(0.5, 1);
            GL.Vertex2(0.5, 0);

            //horizontal-mendatar
            GL.Vertex2(1, 0.5);
            GL.Vertex2(0, 0.5);
        
            GL.End();
        }

8. Draw the vertex and the final optimized route.

void gambar()
        {
            // menggambar Point
            GL.Color3(Color.Red);
            GL.PointSize(4f);
            GL.Begin(BeginMode.Points);
            for (int i = 0; i < latChoose.Count; i++)
            {
                GL.Vertex2(longChoose[i], latChoose[i]);
            }
            GL.End();


            GL.Color3(Color.Black);
            GL.LineWidth(2f);
            GL.Begin(BeginMode.LineLoop);
            if (cekGetRoute)
            {
                foreach (var x in IndexResult)
                {
                    GL.Vertex2(longChoose[x], latChoose[x]);
                }
            }

            GL.End();

            GL.Color3(Color.Green);
            GL.LineWidth(2f);
            GL.Begin(BeginMode.LineLoop);
            if (cekGetRoute)
            {
                foreach (var x in IndexResult2)
                {
                    GL.Vertex2(longChoose[x], latChoose[x]);
                }
            }

            GL.End();
        }

9. Create the viewport and Orthogonal view of the canvas.

 void reshape(Size size)
        {
            //Membuat sumbu orthogonal
            int w = size.Width;
            int h = size.Height;
            GL.Viewport(0, 0, w, h);
            GL.MatrixMode(OpenTK.Graphics.OpenGL.MatrixMode.Projection);
            GL.LoadIdentity();
            GL.Ortho(-0.1, 1.1, -0.1, 1.1, 0.1, -0.1);
            GL.MatrixMode(OpenTK.Graphics.OpenGL.MatrixMode.Modelview);
            GL.LoadIdentity();
        }

10.  Create the redraw function to clear buffer, execute drawCartesian and gambar function. 

void redraw()
        {
            GL.Clear(ClearBufferMask.DepthBufferBit |
            ClearBufferMask.ColorBufferBit |
            ClearBufferMask.AccumBufferBit |
            ClearBufferMask.StencilBufferBit);

            // view graphic
            drawCartesian();
            gambar();

            reshape(glControl1.Size);
            glControl1.SwapBuffers();
        }

11. Because we want redraw function is executed every 100ms, we need a timer.

        private void timer1_Tick(object sender, EventArgs e)
        {
            //Menjalankan fungsi redraw() setiap 100ms
           redraw();    
        }


12. For the last step, we need to find the path using the SavingRoute List and draw them in GLControl that we have created before.

         private void button1_Click(object sender, EventArgs e)
        {
            dataTableNew.Add("O");
            for (int i = 0; i < dataGridView1.Rows.Count; i++)
            {
                dataTableNew.Add(dataGridView1.Rows[i].Cells[0].Value.ToString());
            }

            int count = 0;
            int Batas = 40;
            List<String> tempNewRoute = new List<String>();
            int flag = 0;

            foreach (var x in sr)
            {

                String[] NewRoute = x.Route.Split(',');
                if (flag == 0)
                {
                    for (int i = 0; i < NewRoute.Length; i++)
                    {
                        tempNewRoute.Add(NewRoute[i].ToString().Trim());
                    }
                    flag = 1;
                }
                else
                {
                    for (int i = 0; i < NewRoute.Length; i++)
                    {
                        if (!tempNewRoute.Contains(NewRoute[i].ToString().Trim()))
                            tempNewRoute.Add(NewRoute[i].ToString().Trim());
                    }
                }

            }

            foreach (var x in sr)
            {
                if (x == sr.FirstOrDefault())
                {
                    opRoute.Add("0");
                    opRoute.Add(x.Route[0].ToString().Trim());
                    opRoute.Add(x.Route[2].ToString().Trim());
                    opRoute.Add("0");
                    count += 8;
                }
                else
                {
                    String[] NewRoute = x.Route.Split(',');

                    if ((opRoute.Contains(NewRoute[0]) || opRoute.Contains(NewRoute[1]))
                        && !(opRoute.Contains(NewRoute[0]) && opRoute.Contains(NewRoute[1]))
                       )
                    {
                        String NewStation = opRoute.Contains(NewRoute[0]) ? NewRoute[1] : NewRoute[0];
                        float LastWithNew = float.Parse(dataGridView1.Rows[Int32.Parse(opRoute[opRoute.Count - 2]) - 1].Cells[Int32.Parse(NewStation)].Value.ToString());
                        float FirstWithNew = float.Parse(dataGridView1.Rows[Int32.Parse(NewStation) - 1].Cells[Int32.Parse(opRoute[1])].Value.ToString());
                        opRoute.Insert(LastWithNew > FirstWithNew ? opRoute.Count - 1 : 1, NewStation.ToString().Trim());
                        count += 8;
                    }
                }
            }

            int index = 0;
            foreach (var y in opRoute)
            {
                if (opRoute.Count - 1 == index)
                    ResultRoute += y;
                else ResultRoute += y + " - ";
                index++;
            }
            TempList = ResultRoute.Trim().Split('-');
            TempList = TempList.Where(a => !a.Equals("")).ToArray();
            foreach (var x in TempList)
            {
                SaveResult.Add(x.ToLowerInvariant().Trim().Equals("0") ? "O" : dataGridView1.Rows[Int32.Parse(x) - 1].Cells[0].Value.ToString());
            }
            for (int i = 0; i < SaveResult.Count; i++)
            {
                if (i == 0 || i == SaveResult.Count - 1)
                    IndexResult.Add(0);
                else
                {
                    for (int j = 0; j < SaveChoose.Count; j++)
                    {
                        if (SaveResult[i].ToLowerInvariant().Trim().Contains(SaveChoose[j].ToLowerInvariant().Trim()))
                            IndexResult.Add(j);
                    }
                }
            }
            cekGetRoute = true;
        }

Here's the final result:


From the result above, we can conclude that the final path is : O - C - B - E - D - A - O

That's all of this tutorial. Thanks and see you next time :).


ċ
Research.zip
(2713k)
Sujono _,
Dec 23, 2014, 2:35 AM
ċ
savings.sql
(4k)
Sujono _,
Dec 23, 2014, 2:35 AM