数据结构
- 节约里程表
/**
* 包含节约里程，起点、终点（节约里程表的数据结构）
*
*/
public class Path {
public double save_distance;//节约里程
public int head; //起点
public int tail; //终点
public Path(int head,int tail,double save_distance){
this.head = head;
this.tail = tail;
this.save_distance = save_distance;
}
public Path(){}
}- 路线表
public class Route {
/**
* 剩余容量
*/
public double residual_load;
/**
* 路线上地点的数组
*/
public ArrayList route;
/**
* 路线总路程
*/
public double distance_count;
}具体算法实现
import java.util.ArrayList;
import com.tool.GetDate;
import com.bean.Path;
import com.bean.Route;
/**
* @instruction 节约里程算法
*/
public class Distance {
static double[][] minPath;//最短路线矩阵
static double[] demand; //每个点的需求量
static double whole_capacity; //最大载货量
static int num = 5; // 配送点的数量
static ArrayList<Route> route_result = new ArrayList<Route>(); //路线数组
static ArrayList<Path> save_distance;//节约里程
public static void main(String[] args) {
// 从文件中读取最短路径矩阵和每个点的需求量（文件在data目录下，使用了com.tool中的工具类）
minPath = GetDate.readCSV_distance();
demand = GetDate.readCSV_demand();
whole_capacity = 4; // 最大载货量
num = 5; //配送点数量
//计算节约里程
save_distance = Distance.process(demand, minPath);
//计算节约路线
find_path();
//组织输出，更符合阅读习惯（标号从0更改到1），增加起点终点
System.out.println("-----------------------------------------");
System.out.println("最终输出");
int count = 0;
for (Route r : route_result) {
ArrayList routes = r.route;
System.out.print("P0");
for (int i = 0; i < routes.size(); i++) {
int n = (int)routes.get(i) + 1;
System.out.print("-P" + n + "-");
}
System.out.print("P0");
count += r.distance_count;
System.out.println(",行驶里程：" + r.distance_count);
}
System.out.println("总行驶里程：" + count + "公里");
}
/**
* 根据节约里程表，寻找节约路线
*/
public static void find_path(){
//用来标记该点是否被添加过
boolean isAdd[] = new boolean[num]; //已经添加过的是true
for(boolean i:isAdd)i=false; //初始化，为false
//按照从大到小的顺序考察（i,j）两点路线，满足以下几点
//（1）i,j 不在同一条线路上
//（2）i,j 均与基点相邻
//（3）线路上的需求量不超过载重量（whole_capacity >= residual_load）
//遍历考察(i,j)，直到考察完所有的。
for(Path p: save_distance){//这是foreach的写法，使用迭代效率高，且不需考虑数组下标问题
//save_distance中已经是排好序的，所有按照顺序遍历即可
if(minPath[p.head][0] == 0 && minPath[p.tail][0] == 0)continue; //排除（2）
//初始化一条路线
Route tempR = new Route();
tempR.route = new ArrayList();
tempR.residual_load = whole_capacity;
tempR.distance_count = 0;
if(!isAdd[p.head] && !isAdd[p.tail]){//head和tail都不在路线内
if(tempR.residual_load < demand[p.head] + demand[p.tail]) continue; //判断条件（3），不能过载
tempR.route.add(p.head); //添加head
tempR.route.add(p.tail); //添加tail
isAdd[p.head] = true; isAdd[p.tail] = true; //标记已添加过
tempR.residual_load -= (demand[p.head] + demand[p.tail]); //更新剩余载重
tempR.distance_count += minPath[p.head][0]*2 + minPath[p.tail][0]*2 - p.save_distance;//更新里程
}else if(!isAdd[p.head] && isAdd[p.tail]){//head不在，tail在
//那么应当添加到 tail 在的那条线路里
int i = find(p.tail);
if(route_result.get(i).residual_load < demand[p.head]) continue; //判断条件（3），不能过载，是tail所在路线的载重
route_result.get(i).route.add(i,p.head);//添加head,到tail前
route_result.get(i).residual_load -= demand[p.head]; //更新剩余载重（注意，更新的是tail所在路线的载重）
isAdd[p.head] = true;//标记已添加过
route_result.get(i).distance_count += (minPath[p.head][0]*2 - p.save_distance);//更新里程
}else if(isAdd[p.head] && !isAdd[p.tail]){//tail不在，head在
//那么应当添加到 head 在的那条线路里
int i = find(p.head);
if(route_result.get(i).residual_load < demand[p.tail]) continue; //判断条件（3），不能过载，是head所在路线的载重
route_result.get(i).route.add(p.tail);//添加tail，到head后
route_result.get(i).residual_load -= demand[p.tail]; //更新剩余载重（注意，更新的是head所在路线的载重）
isAdd[p.tail] = true;//标记已添加过
route_result.get(i).distance_count += (minPath[p.tail][0]*2 - p.save_distance);//更新里程
}else{
continue; //都在，则跳过
}
if(tempR.route.size() >= 1){//路线里有超过一个送货点，那么添加
route_result.add(tempR);
}
}
//节约里程（i,j）遍历结束
}
/**
* 在route_result中寻找pos点所在的线路
* @param pos
* @return 返回线路在route_result当中的索引
*/
public static int find(int pos){
for(int i = 0; i < route_result.size(); i++){
ArrayList temp = route_result.get(i).route;
for(int j = 0; j < temp.size(); j++){
if((int)temp.get(j) == pos)return i;
}
}
return -1; //没找到返回-1
}
/**
*
* @param demand
* 需求量
* @param whole_capacity
* 最大载货量
* @param minPath
* 短路径矩阵(对称)
* @return 返回从大到小排好的节约里程
*/
public static ArrayList process(double[] demand, double[][] minPath) {
double[][] save_distance = new double[num][num];
// 计算节约里程，将数据保存到Path类型的ArrayList当中
ArrayList<Path> Save_distance = new ArrayList<Path>();
// 配送点数量为num
for (int i = 0; i < num; i++) {
for (int j = 0; j < i; j++) {
// S(i,j)=C(i,0)+C(0,j)-C(i,j) savedistance比minPath要少一列，所以加一
save_distance[i][j] = minPath[j][0] + minPath[i][0] - minPath[i][j + 1];
save_distance[j][i] = save_distance[i][j];
if(save_distance[i][j] == 0)continue; //没有节约里程的不需要添加
Path path = new Path(i, j, save_distance[i][j]);
Save_distance.add(path);
// 注意，这里的i，j表示的是第几个点，从0开始数
}
}
// 测试所求节约里程是否正确
System.out.println("节约里程矩阵");
for(int i = 0; i < num; i++){
for(int j = 0; j < num; j++){
System.out.print(save_distance[i][j]+"。");
}
System.out.println();
}
//测试结束
// 对Save_distance 按照save_distance属性值的大小进行递减排序
int len = Save_distance.size();// Save_distance元素个数
for (int i = 0; i < len; i++) { // 单冒泡排序
for (int j = 0; j < len - i - 1; j++) {
Path x = Save_distance.get(j); // j位置上的值
Path y = Save_distance.get(j + 1); // j+1位置上的值
// 大到小排序，如果前一个小于后一个，那么交换这两个位置上的值
if (x.save_distance < y.save_distance) {
Path temp = x; // 临时变量，用于交换
Save_distance.set(j, y);
Save_distance.set(j + 1, temp);
}
}
}
//测试是否排好序
System.out.println("--------------------------------");
System.out.println("从大到小排序结果");
System.out.println("\t"+"head"+"\t"+"tail"+"\t"+"save_distance");
for(int i = 0; i < Save_distance.size(); i++){
System.out.print("\t" + Save_distance.get(i).head);
System.out.print("\t" + Save_distance.get(i).tail);
System.out.println("\t" + Save_distance.get(i).save_distance);
}
//测试结束
return Save_distance;
}
}
备注：
测试数据写到了csv里，方便读取。
- 最短距离矩阵
- 需求矩阵
- 读文件代码
import java.io.IOException; import java.nio.charset.Charset; import java.util.ArrayList; import java.util.Arrays; /** * @instruction 工具类，用来从文件读取最短路径数据矩阵、需求量数据矩阵 * */ public class GetDate { final static int MAX = 10; //最大节点数 public static double[][] readCSV_distance() { // 用来保存数据,默认为10 double [][]minPath = new double [MAX][MAX]; try { // 定义一个CSV路径 String csvFilePath = "data/data_distance.csv"; // 创建CSV读对象 CsvReader reader = new CsvReader(csvFilePath, ',', Charset.forName("UTF-8")); // 跳过表头 reader.readHeaders(); // 逐行读入除表头的数据 int len = reader.getHeaderCount(); int i=0,j; while (reader.readRecord()) { String [] temp = reader.getRawRecord().split(","); for(j = 0; j < temp.length; j++){ minPath[i][j] = Double.parseDouble(temp[j]); } i++; } reader.close(); } catch (IOException e) { e.printStackTrace(); } return minPath; } public static double[] readCSV_demand() { // 用来保存数据,默认为10 double []demand = new double [MAX]; try { // 定义一个CSV路径 String csvFilePath = "data/data_demand.csv"; // 创建CSV读对象 CsvReader reader = new CsvReader(csvFilePath, ',', Charset.forName("UTF-8")); // 跳过表头 reader.readHeaders(); // 逐行读入除表头的数据 int len = reader.getHeaderCount(); int i=0,j; while (reader.readRecord()) { String [] temp = reader.getRawRecord().split(","); for(j = 0; j < temp.length; j++){ demand[j] = Double.parseDouble(temp[j]); } i++; } reader.close(); } catch (IOException e) { e.printStackTrace(); } return demand; } }参考了这里的一些内容。
版权声明：本文为the_power原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。