您好,欢迎来到中国大物流新闻资讯信息发布网_物流公司货运查询-中国最专业的物流平台!

物流配送路径最优算法,让最后一公里配送路径尽可能短

2019/4/3 17:23:17 0人评论 5373次浏览 分类:中国大物流首页>新闻资讯 > 新闻快讯 > 国内资讯

1. 物流企业为N个客户配送产品,企业有一台卡车,客户的包裹均为小件,一车可以全部装载。请设计配送路径,使得配送所通过的总路程最短。

2. 分别做三次实验,每次试验中客户数分别为N = 10, 100, 1000

3. 每次实验按下述步骤进行:

(1) 客户分别为1, 2, …, N,随机产生每两个客户之间的距离

(2) 卡车从物流企业出发,遍历所有客户,每个客户只需访问一次,最后卡车要返回物流企业

(3) 记录下卡车访问客户的顺序π,同时计算卡车所通过的总路程L

(4) 首先按顺序遍历,即访问客户的顺序为1, 2, …,N,记录总路程L0。然后,请设计配送方法,所得配送总路程L1,计算改进的百分比α:

α = (L1 – L0)/L0

若α> 30%,实验成功。记录下此时的算法、访问顺序和总路程。

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector> 
#define maxDistance 100 // 随机取2个客户之间距离的最大上限 
#define N 50 //定义客户数为N 
#define maxNumber 1000000 
using namespace std;
typedef struct listNode{
int value;
struct listNode * next;

} * list;

void initial (float distanceMatrix [N+1][N+1] )//初始化距离矩阵的值 
{ for(int i=0;i<N+1;i++)
{for(int j=0;j<=i;j++)
{ srand((int)time(NULL)+i*130+j*10); //设置随机函数的种子 
distanceMatrix[i][j]=rand()%maxDistance+1;//随机数赋值(1~maxDistance) 

distanceMatrix[j][i]= distanceMatrix[i][j];
if(j==i)
{ distanceMatrix[j][i]=0;
distanceMatrix[i][j]=0;
}



}






//以下是范例:共三个客户: 
//解题思想: 假设首先选择从物流中心到(0)到客户 1,那么只要求1到0最短路径。然后求1到0最短路径又可以继续分为子问题。。。
//方法缺陷 : 送货车回来的路可以是重复的,而本算法只假定了 每次路过不同节点。
//对于解决旅行商问题 ,如此的动态规划并不是最佳的算法。算法性能较差,对于 10*10的矩阵已经很吃力了。 


for(int i=0;i<N+1;i++) //打印距离矩阵 
{
for(int j=0;j<N+1;j++)
{
cout<<distanceMatrix[i][j]<<" ";
}
cout<<endl;
}

}
float l0=0;
void calculateL0 (float distanceMatrix [N+1][N+1]) //计算L0 ,存储在l0中 

for(int i=0;i<N+1;i++ )
{l0=l0+distanceMatrix[i][(i+1)%(N+1)];

}

cout<<"L0:"<<l0<<endl; 
}


int path[N][N+1];




int getMinDisatance(float distanceMatrix [N+1][N+1],int cur,vector<int> notSolvedV,list & L)

vector<int>::iterator j;
for(j=notSolvedV.begin();j!=notSolvedV.end();j++)
{if (cur==*j)
{notSolvedV.erase(j);
break; 
}
}
L=new listNode;
L->value=cur; 

if(notSolvedV.size()==0)
{ L=new listNode;
L->value=cur;
L->next=NULL; 
return distanceMatrix[cur][0] ;

else
{float min=maxNumber;

for(int i=0;i<notSolvedV.size();i++)
{list p;
float x=distanceMatrix[cur][notSolvedV[i]]+getMinDisatance(distanceMatrix,notSolvedV[i],notSolvedV,p);
if(x<min)
{min=x; 
L->next=p; 
}
else

while(p!=NULL) 
{list u=p->next;
delete p;
p=u;
}
}
}
return min;
}
}
void myDesign(float distanceMatrix [N+1][N+1]) 
{ vector<int> notSolvedV; 
for(int i=0;i<N+1;i++)
notSolvedV.push_back(i);
list L;//链表存储路径 

float l1=getMinDisatance(distanceMatrix,0,notSolvedV,L);
while(L!=NULL)
{cout<<L->value<<"-->";
L=L->next;
}
cout<<"0";
cout<<endl;
cout<<"L1: "<< l1<<endl;

cout<<"α:"<<(l0-l1)/l0<<endl; 


int main()
{ float distanceMatrix [N+1][N+1];//任意2个(客户+物流中心)之间的距离 用矩阵存储 设置节点0为物流中心 
initial(distanceMatrix); 
calculateL0 (distanceMatrix);
myDesign(distanceMatrix) ;
return 0;
}
 

返回中国大物流首页

版权所有:中国大物流 站点地图

Copyright © 2015 - 2022 www.chinada56.cn All Rights Reserved

 
QQ在线咨询
广告合作
文章代发
请点击QQ在线咨询