We help IT Professionals succeed at work.

Help with my logic (.NET)

PhilippeRenaud
PhilippeRenaud used Ask the Experts™
on
Hello EE,

I need to code this in .NET but no idea how.. but I have the logic :

Lets say we have Point A, Point B, Point C and Point D.
We have 2 cars at Point A.

Distance from A to B is 5 miles.
Distance from A to C is 17 miles.
Distance from A to D is 11 miles.

Point A is the main warehouse.


Let's say also that we have priority 1 wich is the time ordered and Priority 2 wich is the distance.

Let's say time ordered for Point B is 13:00
Let's say time ordered for Point C is 12:00
Let's say time ordered for Point D is 14:00

Ok so what it needs to calculate is... from A wich car will go to the first client always remembering the priority. So here since both car are at the same place it doens matter wich car.

Lets say Car 1 leaves and of course it will go at Point C because time is 12:00.

So because Car 1 left.. car 2 is still at warehouse it will go at Point B so the car can be useful while Car 1 is going to Point C.

From there we need to compare is car 1 or car 2 will go to Point D ?
Lets say distance from B to D is 12 miles and distance from C to D is 9 miles

well it should be Car 2.


is there a way we can code this in vb.net ??
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®

Commented:
You may need to introduce another parameter,time taken to cover a distance / mile. May not be obviously necessary with the scenario you have above, but it will be necessary as the permutation gets more complex.

In the meantime, I'll try and wrap my mind around what we have and post as soon as I think I got a solution.

Author

Commented:
You are right.
Since right now I am not sure what is the time taken for each i will put random amount of time:

From A to B : 10 minutes
From A to C :  25 minutes
From B to D : 21 minutes
From C to D : 12 minutes


Of course this is hardcoded.. actually if you want you could generate a random amount of time instead of using this.. to test if the code works for every combinations..

Many thanks Nepaluz.. this would be great help.. wish I could give more points.
Top Expert 2011

Commented:
Is this a real business problem or a course assignment?

In a real business scenario there are many other variables involved (size of the vehicle, size/weight of the packages, need to refuel, etc), which make any solution quite complex.

Here is an introduction to the problem domain:

Vehicle Routing and Scheduling
http://www.ima.umn.edu/talks/workshops/9-9-13.2002/savelsbergh/VRP_part1.pdf

or Google for "Vehicle Routing Model"

I hope this helps.

Author

Commented:
its business problem but its not for the Maximal efficiency at the penny...

if we can make it better its fine no need to reach fuel weight etc..

Author

Commented:
So Nepaluz, any luck yet?
with only 2 cars and 3 deliveries you could just run all possibilities.

you'll need a basic routine that given two points returns the travel time.

also you'll need to assign some sort of on time (or late) factor to each delivery.

just loop through all routes for each car

Car 1 A-B
Car 2 A-C-D then save this as the 'best' time.

Car 1 A-B
Car 2 A-D-C does this beat the 'best' time? save this route and 'best' time

Car 1 A-C
Car 2 A-B-D and so on

Note if at any time you exceed the 'best' time abandon this route option
Oh to see an awesome video on getting stuff to the right place at the right time watch this
http://www.ted.com/talks/lang/en/mick_mountz_the_hidden_world_of_box_packing.html
When you say is there a way to code this in vb.net -- yes, definitely. Is your question about the word problem or about .net?

Author

Commented:
Actually i came here because i need help to code it yes.. this goes beyond what im capable of

not a developer expert like you guys
Oh, well in general we don't code entire projects. I think you're going to have to hire a programmer for the project. There are many details that would be required to even write the routine that returns the travel time. Such as, what data base do you have? How are locations identified (street address or lati longi numbers? Will the routes be changing as new orders are entered into the system? What happens when a car gets a flat tire? Can the other car meet the first car to get the packages to then complete the deliveries?

These are just the quick questions off the top of my head.
I agree with Michael701. The question's answer is way too large to get help with on EE.
Tier 3 Senior Technical Support Engineer
Commented:
Yes, the solution would be a component that is already available. Beside that, encoding the Vehicle Routing Problem in VB.NET is not usual.

There are already problem solver components to be used in C# or VB.NET available: https://www.google.com/search?q=vehicle+routing+vb.net

For example DNA JOpt.Net

There are even opensource implementations you can use: http://sourceforge.net/projects/vrpsolver/?source=directory. But as said, VB.NET is not the primary language suitable for such problems.

~josef

Author

Commented:
Youre right thanks!
hjgodeTier 3 Senior Technical Support Engineer

Commented:
Hi and thanks for the points. As I had some time and this Vehicle Routing Prolem scenario is small, I did a class in C# to solve your first question:

The code implements a point class with the ccordinates of the points. Then there is a distance calculator, that cals the distance between two points (pythagoras, back to school). Finally there is a function that cals the nearest point of a list against one source point.

There is currently no priority included in the class. You may add one and then have to decide between priority or distance based on a unknown-to-me weighting. Possibly a point system, for example prio 10 would dived the distance by 10 and then compared to the others.

using System;
using System.Collections.Generic;

namespace VRPsimple
{
	/* Sample data
	10
	 9 A
	 8
	 7                 B
	 6
	 5     C
	 4
	 3           D 
	 2
	 1
	 0 1 2 3 4 5 6 7 8 9 1
	                     0		
	 A (1,9)
	 B (9,7)
	 C (3,5)
	 D (6,3)
	 */
	/// <summary>
	/// class to examine the smallest destination for
	/// two source points at one target point
	/// source could be two cars
	/// target could be one destination
	/// </summary>
	public class simpleVRPclass
	{
		public List<point> testPoints;
		public string testString;
		public simpleVRPclass(){
			testPoints= new List<point>();
			testPoints.Add(new point(1,9,point.pointType.target, "A"));
			testPoints.Add(new point(9,7,point.pointType.target, "B"));
			testPoints.Add(new point(3,5,point.pointType.target, "C"));
			testPoints.Add(new point(6,3,point.pointType.target, "D"));                              
			string txt="";
			txt += " 9 A\r\n";
			txt += " 8\r\n";
			txt += " 7                 B\r\n";
			txt += " 6\r\n";
			txt += " 5     C\r\n";
			txt += " 4\r\n";
			txt += " 3           D \r\n";
			txt += " 2\r\n";
			txt += " 1\r\n";
			txt += " 0 1 2 3 4 5 6 7 8 9 1\r\n";
			testString=txt;
		}
		public point getPointByName(string s){
			point p=null;
			foreach(point p1 in testPoints){
				if(p1._name==s){
					p = p1;
					return p;
				}
			}
			return p;
		}
		public static double distance(point a, point b){
			//as the sqrt is not perfect, we check something before
			if(a._x==b._x && a._y==b._y)
				return (double)0;
			if(a._x==b._x)
				return (double)Math.Abs(a._y-b._y);
			if(a._y==b._y)
				return (double)Math.Abs(a._x-b._x);
			double _distance=System.Math.Sqrt( 
			                                  (double)((a._x-b._x)*(a._x-b._x)) + 
			                                  (double)((a._y-b._y)*(a._y-b._y))
			                                  );
			return _distance;
		}
		//public double _distance;
		 
		/// <summary>
		/// return the point which has the smallest destination to target
		/// </summary>
		/// <param name="sourcePoints">
		/// A <see cref="List<Point>"/>
		/// a list of source points
		/// </param>
		/// <param name="targetPoint">
		/// A <see cref="point"/>
		/// </param>
		/// <returns>
		/// A <see cref="point"/>
		/// </returns>
		public static point smallest(List<point> sourcePoints, point targetPoint){
			double minDistance=Double.MaxValue;
			double distanceTemp=Double.MaxValue;
			point nearestPoint=null;
			//calc distance for all possible pairs
			foreach(point p in sourcePoints){
				distanceTemp = distance(targetPoint, p);
				if(distanceTemp<minDistance){
					minDistance=distanceTemp;
					nearestPoint=p;
				}
			}
			return nearestPoint;
		}
		
		public static double smallest(System.Collections.Generic.List<double> pts){
			double min=Double.MaxValue;
			double minTemp=Double.MaxValue;
			double[] ptsArr=pts.ToArray();
			for(int i=0; i<ptsArr.Length-1; i++){
				minTemp = System.Math.Min(ptsArr[i], ptsArr[i+1]);
				if(minTemp<min)
					min=minTemp;
			}
			return min;
		}
	}
	public class point{

		public int _x{get;set;}
		public int _y{get;set;}
		public enum pointType{
			none,
			source,
			target
		}
		public pointType _pointType {get; set;}
		public point(int x, int y){
			_x=x;
			_y=y;
		}
		public string _name{get;set;}
		public point(int x, int y, pointType pType){
			_x=x;
			_y=y;
			_pointType=pType;
		}
		public point(int x, int y, pointType pType, string sName){
			_x=x;
			_y=y;
			_pointType=pType;
			_name=sName;
		}
		public point moveTo(int x, int y){
			this._x=x;
			this._y=y;
			return this;
		}
		public override string ToString ()
		{
			return string.Format ("[point: _x={0}, _y={1}, _pointType={2}, _name={3}]", _x, _y, _pointType, _name);
		}
		}
}

Open in new window


Then in a simple form with a TextBox txtOut docked inside I have this run routine:
		private void run(){
			VRPsimple.simpleVRPclass vrp= new VRPsimple.simpleVRPclass();
			addText(vrp.testString);
			point Car1 = new point(1,9,point.pointType.source, "Car1");
			addText("Added " + Car1.ToString());
			point Car2 = new point(1,9,point.pointType.source, "Car2");
			addText("Added " + Car2.ToString());
			
			foreach(point p in vrp.testPoints){
				addText(p.ToString());
				addText("\tdistance Car1 to "+ p._name + " = " + simpleVRPclass.distance(Car1,p).ToString());
			}
			Car2.moveTo(6,3);
			addText("Car2 moved: " + Car2.ToString());
			List<point> carList = new List<point>();
			carList.Add(Car1);
			carList.Add(Car2);
			addText("build source list with Car1 and Car2");
			point targetPoint = vrp.getPointByName("C");
			if(targetPoint==null){
				addText("Could not find point 'C' in testList");
				return;
			}
			addText("Getting nearest Car for point 'C'");
			point nearest = simpleVRPclass.smallest(carList, targetPoint);
			if(nearest!=null){
				addText("found nearest car to point 'C' = " + nearest.ToString());
			}
			else
				addText("Could not find nearest car to point 'C'");
		}

Open in new window


And here is the output:
 9 A
 8
 7                 B
 6
 5     C
 4
 3           D 
 2
 1
 0 1 2 3 4 5 6 7 8 9 1

Added [point: _x=1, _y=9, _pointType=source, _name=Car1]
Added [point: _x=1, _y=9, _pointType=source, _name=Car2]
[point: _x=1, _y=9, _pointType=target, _name=A]
	distance Car1 to A = 0
[point: _x=9, _y=7, _pointType=target, _name=B]
	distance Car1 to B = 8.24621125123532
[point: _x=3, _y=5, _pointType=target, _name=C]
	distance Car1 to C = 4.47213595499958
[point: _x=6, _y=3, _pointType=target, _name=D]
	distance Car1 to D = 7.81024967590665
Car2 moved: [point: _x=6, _y=3, _pointType=source, _name=Car2]
build source list with Car1 and Car2
Getting nearest Car for point 'C'
found nearest car to point 'C' = [point: _x=6, _y=3, _pointType=source, _name=Car2]

Open in new window


Possibly the one or other takes the code. You may easily convert it to VB.NET using an online converter.

regards

Josef