form1.cs

基于遗传算法的车辆路径优化的ＣＳＨＡＲＰ程序

using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;

namespace vrpnewGASA
{
	/// <summary>
	/// Form1 的摘要说明。
	/// </summary>
	public class Form1 : System.Windows.Forms.Form
	{
		private System.Windows.Forms.Button button1;
		private System.Windows.Forms.TextBox outputTextBox;
		/// <summary>
		/// 必需的设计器变量。
		/// </summary>
		private System.ComponentModel.Container components = null;

		public Form1()
		{
			//
			// Windows 窗体设计器支持所必需的
			//
			InitializeComponent();

			//
			// TODO: 在 InitializeComponent 调用后添加任何构造函数代码
			//
		}

		/// <summary>
		/// 清理所有正在使用的资源。
		/// </summary>
		protected override void Dispose( bool disposing )
		{
			if( disposing )
			{
				if (components != null) 
				{
					components.Dispose();
				}
			}
			base.Dispose( disposing );
		}

		#region Windows 窗体设计器生成的代码
		/// <summary>
		/// 设计器支持所需的方法 - 不要使用代码编辑器修改
		/// 此方法的内容。
		/// </summary>
		private void InitializeComponent()
		{
			this.button1 = new System.Windows.Forms.Button();
			this.outputTextBox = new System.Windows.Forms.TextBox();
			this.SuspendLayout();
			// 
			// button1
			// 
			this.button1.Location = new System.Drawing.Point(264, 16);
			this.button1.Name = "button1";
			this.button1.Size = new System.Drawing.Size(112, 32);
			this.button1.TabIndex = 0;
			this.button1.Text = "display";
			this.button1.Click += new System.EventHandler(this.button1_Click);
			// 
			// outputTextBox
			// 
			this.outputTextBox.Location = new System.Drawing.Point(208, 72);
			this.outputTextBox.Multiline = true;
			this.outputTextBox.Name = "outputTextBox";
			this.outputTextBox.ScrollBars = System.Windows.Forms.ScrollBars.Both;
			this.outputTextBox.Size = new System.Drawing.Size(248, 200);
			this.outputTextBox.TabIndex = 1;
			this.outputTextBox.Text = "";
			// 
			// Form1
			// 
			this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);
			this.ClientSize = new System.Drawing.Size(680, 326);
			this.Controls.Add(this.outputTextBox);
			this.Controls.Add(this.button1);
			this.Name = "Form1";
			this.Text = "Form1";
			this.ResumeLayout(false);

		}
		#endregion

		/// <summary>
		/// 应用程序的主入口点。
		/// </summary>
		[STAThread]
		static void Main() 
		{
			Application.Run(new Form1());
		}
		public class pp                            //此程序是2002年6月的计算机集成制造系统的程序的改进
		{
			public int cityNum=50;//原始的城市数
			public int cNumber=51;//插入站点后的城市数
			public int vehicleNumber=5;
			public int vehicleCapacity=160;// 车的容量
			public int maxTime=1000;//maximize iteration;
			public int popSize=5;//maximize population
			public int jrand;//creative randomnumber
			public int bestChroms;
			public double pCross=0.85;// probability of chrom crossover
			public double pMutation=0.03;// probability of chrom mutation
			public double[] oldrand=new double[200];
		}
        pp disp=new pp();
		private void calculate(ref double[] distance,ref double[] demand,ref double[] polarAngle)
		{
			int[] xcoordate={30,37,49,52,20,40,21,17,31,52,51,42,31,5,12,36,52,27,17,13,57,62,42,16,8,7,27,30,43,58,58,
								37,38,46,61,62,63,32,45,59,5,10,21,5,30,39,32,25,25,48,56};
			int[] ycoordate={40,52,49,64,26,30,47,63,62,33,21,41,32,25,42,16,41,23,33,13,58,42,57,57,52,38,68,48,67,48,
								27,69,46,10,33,63,69,22,35,15,6,17,10,64,15,10,39,32,55,28,37};
			int[] initdemand={0,7,30,16,9,21,15,19,23,11,5,19,29,23,21,10,15,3,41,9,28,8,8,16,10,28,7,15,
								 14,6,19,11,12,23,26,17,6,9,15,14,7,27,13,11,16,10,5,25,17,18,10};
			for(int i=0;i<disp.cNumber;i++)
			{
				for(int j=0;j<disp.cNumber;j++)
				{
					distance[i*disp.cNumber+j]=Math.Sqrt(Math.Pow((xcoordate[i]-xcoordate[j]),2)+Math.Pow((ycoordate[i]-
						ycoordate[j]),2));
				}
				demand[i]=initdemand[i];
			}
			int[] polarXCoordate=new int[disp.cityNum];
			int[] polarYCoordate=new int[disp.cityNum];
			for(int i=1;i<xcoordate.Length;i++)
			{
				polarXCoordate[i-1]=xcoordate[i]-xcoordate[0];
				polarYCoordate[i-1]=ycoordate[i]-ycoordate[0];
			}
			for(int i=0;i<polarXCoordate.Length;i++)
			{
				double polar;
				polar=Math.Pow(polarXCoordate[i],2)+Math.Pow(polarYCoordate[i],2);
				if((polarXCoordate[i]>=0)&&(polarYCoordate[i]>=0))
				{
					polarAngle[i]=Math.Asin(polarYCoordate[i]/polar)*360/Math.PI;
				}
				if((polarXCoordate[i]<0)&&(polarYCoordate[i]>=0))
				{
					polarAngle[i]=180-Math.Asin(polarYCoordate[i]/polar)*360/Math.PI;
				}
				if((polarXCoordate[i]<0)&&(polarYCoordate[i]<0))
				{
					polarAngle[i]=180-Math.Asin(polarYCoordate[i]/polar)*360/Math.PI;
				}
				if((polarXCoordate[i]>=0)&&(polarYCoordate[i]<0))
				{
					polarAngle[i]=360+Math.Asin(polarYCoordate[i]/polar)*360/Math.PI;
				}
			}
		}
		private void quickSort(ref double[] distance,int startPos,int endPos)
		{
			int i,j;
			double number;
			number=distance[startPos];
			i=startPos;
			j=endPos;
			
			while(i<j)
			{
				while((distance[j]>=number)&&(i<j))
				{
					--j;
				}
				distance[i]=distance[j];
				while((distance[i]<=number)&&(i<j))
				{
					++i;
				}
				distance[j]=distance[i];
			}
			distance[i]=number;
			if(i-1>startPos)
			{
				quickSort(ref distance,startPos,i-1);
			}
			if(endPos>i+1)
			{
				quickSort(ref distance,i+1,endPos);
			}
		}
		pp initp=new pp();
		private void initiation(double[] distance,double[] demand,ref int[] numberOfVehicle,
			ref int[,,] routeLength,ref int[,,] chroms)
		{
			for(int i=0;i<chroms.GetLength(0);i++)
			{
				double[] cost=new double[initp.cNumber];
				double[] beforeOfquickSort=new double[initp.cNumber];
				int[] customerIndex=new int[initp.cNumber];
				int[] tempChroms=new int[initp.cityNum];
				Random randNumber=new Random();//create a new start point
				int firstCustomer;
				firstCustomer=randNumber.Next(1,initp.cNumber);
				for(int j=1;j<cost.Length;j++)
				{
					cost[j]=distance[firstCustomer*initp.cNumber+j];
                    beforeOfquickSort[j]=cost[j];
				}
                quickSort(ref cost,1,initp.cNumber-1);
				
				for(int j=1;j<cost.Length;j++)
				{
					for(int k=1;k<cost.Length;k++)
					{
						if((cost[j]-beforeOfquickSort[k]<1e-5)&&(cost[j]-beforeOfquickSort[k]>-1e-5))
						{
							customerIndex[j]=k;
							beforeOfquickSort[k]=-1;
							break;
						}
					}
				}
				
				int unroutedCustomerOfNumber=initp.cNumber;
				int routedCustomer=0;
				int routeOfNumber=0;
				while(routedCustomer<initp.cityNum)
				{
					double totalVehicleCapacity=0.0;
					bool reapeatCapacity=false;
					int startNumberOfCustomer;
					if(unroutedCustomerOfNumber>3)
					{
						startNumberOfCustomer=3;
					}
					else 
					{
						startNumberOfCustomer=unroutedCustomerOfNumber-1;
					}
					for(int k=1;k<=startNumberOfCustomer;k++)
					{
                        totalVehicleCapacity+=demand[customerIndex[k]];
						if(totalVehicleCapacity>=initp.vehicleCapacity)
						{
							reapeatCapacity=true;
							break;
						}
                        routedCustomer++;
	                    routeLength[i,routeOfNumber,0]++;
						chroms[i,numberOfVehicle[i],routeLength[i,routeOfNumber,0]]=customerIndex[k];
						tempChroms[k]=customerIndex[k];
					}

					double[] tempCost=new double[initp.cityNum];
					for(int k=4;k<unroutedCustomerOfNumber;k++)
					{
						for(int j=1;j<k-1;j++)
						{
							tempCost[j]=distance[customerIndex[j]*initp.cNumber+customerIndex[k]]
								+distance[customerIndex[k]*initp.cNumber+customerIndex[j+1]]
								-distance[customerIndex[j]*initp.cNumber+customerIndex[j+1]];
						}
						tempCost[k-1]=distance[customerIndex[1]*initp.cNumber+customerIndex[k]]
							+distance[customerIndex[k]*initp.cNumber+customerIndex[k-1]]
							-distance[customerIndex[1]*initp.cNumber+customerIndex[k-1]];
						double minimize;
						int flag=1;
						minimize=tempCost[1];
						for(int t=2;t<k;t++)
						{
							if(minimize-tempCost[t]>1e-8)
							{
								minimize=tempCost[t];
								flag=t;
							}
						}
						totalVehicleCapacity+=demand[customerIndex[k]];
						if(totalVehicleCapacity>=initp.vehicleCapacity)
						{
							reapeatCapacity=true;
							break;
						}
						if(flag<k-1)
						{
							routedCustomer++;
                            routeLength[i,routeOfNumber,0]++;
							chroms[i,numberOfVehicle[i],flag+1]=customerIndex[k];
							for(int t=flag+2;t<=k;t++)
							{
								chroms[i,numberOfVehicle[i],t]=tempChroms[t-1];
							}
						}
						else
						{
							routeLength[i,routeOfNumber,0]++;
							routedCustomer++;
							chroms[i,numberOfVehicle[i],flag+1]=customerIndex[k];
						}
						for(int t=1;t<=k;t++)
						{
							tempChroms[t]=chroms[i,numberOfVehicle[i],t];
						}
					}
//                    outputTextBox.Text+="routLength="+routeLength[i,routeOfNumber,0]+" ";
//                    outputTextBox.Text+="numberOfVehicle="+numberOfVehicle[i]+" ";
					if(reapeatCapacity==true)
					{   
						numberOfVehicle[i]++;
						
						int[] unSelectCustomer=new int[initp.cityNum];
						int unSelectNumber=1;
						
						for(int t=routeLength[i,routeOfNumber,0]+1;t<unroutedCustomerOfNumber;t++)
						{
							unSelectCustomer[unSelectNumber++]=customerIndex[t];
						}
						routeOfNumber=numberOfVehicle[i];
                        unroutedCustomerOfNumber=initp.cNumber-routedCustomer;
						Random reapeatRandNumber=new Random();
						int reapeatNewRoute;
						reapeatNewRoute=unSelectCustomer[reapeatRandNumber.Next(1,unroutedCustomerOfNumber)];
						double[] newCost=new double[unroutedCustomerOfNumber];
						double[] newBeforeOfquickSort=new double[unroutedCustomerOfNumber];
						for(int j=1;j<newCost.Length;j++)
						{
							newCost[j]=distance[reapeatNewRoute*initp.cNumber+unSelectCustomer[j]];
							newBeforeOfquickSort[j]=newCost[j];
						}
						quickSort(ref newCost,1,unroutedCustomerOfNumber-1);
						for(int j=1;j<newCost.Length;j++)
						{
							for(int k=1;k<newCost.Length;k++)
							{
								if((newCost[j]-newBeforeOfquickSort[k]<1e-5)&&(newCost[j]-newBeforeOfquickSort[k]>-1e-5))
								{
									customerIndex[j]=unSelectCustomer[k];
									newBeforeOfquickSort[k]=-1;
									break;
								}
							}
						}
//						for(int j=1;j<newCost.Length;j++)
//						{
//							outputTextBox.Text+=customerIndex[j]+" ";
//						}
//                        outputTextBox.Text+="*************************************";
					}
				}
			}
		}
        pp displayp=new pp();
		private void button1_Click(object sender, System.EventArgs e)
		{
			outputTextBox.Text="";
			double[] distance=new double[displayp.cNumber*displayp.cNumber];
			double[] demand=new double[displayp.cNumber];
			double[] polarAngle=new double[displayp.cityNum];
			calculate(ref distance,ref demand,ref polarAngle);
			
			int[,,] chroms=new int[displayp.popSize,2*displayp.vehicleNumber,displayp.cityNum];
			int[] numberOfVehicle=new int[2*displayp.vehicleNumber];
			int[,,] routeLength=new int[displayp.popSize,2*displayp.vehicleNumber,1];
            initiation(distance,demand,ref numberOfVehicle, ref routeLength,ref chroms);
            outputTextBox.Text+="*************************************";
//			for(int i=0;i<chroms.GetLength(0);i++)
//			{
//				for(int j=0;j<=numberOfVehicle[i];j++)
//				{
//					for(int k=1;k<=routeLength[i,j,0];k++)
//					{
//                         outputTextBox.Text+=chroms[i,j,k]+" ";
//					}
//                    outputTextBox.Text+="*************************************";
//				}
//				outputTextBox.Text+="/////////////////////////////////////";
//			}
		}
	}
}