一，项目简介
如今互联网与电子商务的飞速发展，物流服务行业也日益重要，如何提升物流服务的效率，降低物流服务的成本成为当下人们所关注的内容。大多数的传统物流运输业花费大量的金钱和人力在运输、仓储、配送中，因此这些传统物流企业大多成本高利润低。为了保证物流市场的健康发展，需要有效地支持物流配送，提高物流质量服务。而物流配送活动，作为连接商家和客户的关键环节最应当被重视和优化，从而避免出现物流配送效率低、资源浪费严重和配送成本高等问题，以此来提升我国物流行业的整体发展。
物流配送优化主要可以从2个方面进行优化。一、提高车辆的装载问题:即车辆装载问题（VehicleFillingProblem.VFP）。二、减少车辆运输路径:即车辆装载问题（VehicleRoutingProblem.VRP）。本文将使用IDEA作为开发工具,java作为开发语言，建立货车装载和配送货物的模型，通过算法对VFP和VRP同时进行优化，得到如何进行货物配送才能最优的解决方案。并使用html语言，在web页面上进行动画展示。
目前已经研发完毕，在Web界面上演示效果佳，人机交互效果好，反应较快。同时与未采用该算法的传统配送方案相比，该程序得到的运输方案，货车装载率有了明显提高和运输路途的总里程有显著降低。通过该程序成功实现了物流拼单组合系统，有效提升物流服务的效率
二，环境介绍
语言环境：Java: jdk1.8
数据库：Mysql: mysql5.7
应用服务器：Tomcat: tomcat8.5.31
开发工具：IDEA或eclipse
后台开发技术：Springboot+Mybatis
前台开发技术：html5 + javascript+thymeleaf
三，系统展示
3.1 系统的功能点描述
本系统为物流拼单组合系统,主要功能有查看送货地点，分配货车，查看所有的路径规划，查看单个路径动画，查看所有路径动画。
3.2 系统功能的具体测试
3.2.1 查看送货地点
(1)测试用例:
使用随机数随机生成200个起点一致，终点和货物种类、数量不一致的当日订单，生成随机订单程序核心代码截图如下图5-1所示，库中部分订单数据如下图5-2所示。
图5‑1 生成200个随机订单的核心代码
图5‑2 数据库200个订单部分截图
（2）测试结果:
图5‑3 查看送货地点测试结果
（3）结果描述:
选定时间后，点击查看送货地点，前端向后端发送请求，后端将当日所有订单结果返回，如下图5-4所示:
图5‑4 前端发送请求后端返回结果图。
前端解析json后，在地图上进行标注，显示中文名称和需要配送的体积。
3.2.2 分配货车
(1)测试用例:
有5种货车，分别为体积为600,1000,1400,2200,2500,这五种货车，和5.2.1生成的200个订单。
- 测试结果:
图5‑5 查看送货地点测试结果
- 结果描述:
点击分配货车后，前端向后端发送请求，后端返回如何进行货车分配，前端解析后，显示派出哪种类型的车和派出数量，并计算出满载率并显示在页面上。
图5‑6 前端发送请求后端返回结果图。
3.2.3 查看所有的路径规划
(1)测试用例:
3.2.1生成的200个订单和5.2.2得到的货车分配
- 测试结果:
图5‑7 查看所有的路径规划部分结果
- 结果描述:
点击查看所有路径规划，向后端发送请求，如下图5-8所示后端返回所有路径返回，解析后显示成文字路径，包含了派出哪种类型的车，使用了多少的体积，起点、途经点、终点的名字和向这些地点配送了多少的体积，并将部分参数放在url中，生成超链接，可以通过单击超链接播放动画
图5‑8 前端发送请求后端返回结果图
3.2.4 查看单个路径动画
(1)测试用例:
3.2.3得到的路径
- 测试结果:
图5‑9 查看单个路径动画演示部分结果图
- 结果描述:
动态的展示单次货车配送的起点、途经点、终点名字和配送体积，三角形为模拟货车，绿色为货车行经路线。
3.2.5 查看所有路径动画
(1)测试用例:
3.2.3得到的所有路径
- 测试结果:
图5‑10 查看所有路径动画演示部分结果图
(3)结果描述:
动态的展示当日所有货车配送的起点、途经点、终点名字和配送体积，三角
形为模拟货车，绿色为货车行经路线。
3.3 本章小结
本章主要讲述了系统整体的功能点和对整体功能点的具体测试，包含测试用例，测试结果，结果分析，保证了系统的可用性
四，核心代码展示
业务层具体实现
业务层采用springboot框架。springboot继承了spring的优秀特性：控制反转，面向切面编程等，同时能帮助我们简化开发,减少XML的配置。
业务层主要通过调用持久层的接口获取存在数据库中的某个日期的订单集合。查询订单集合。根据订单上的起始地点id和终点id关联地点表，获得起始地点和终点的经纬度。根据货物id关联货物表可以得到货物的单位体积，与订单上的货物数量相乘就可以得到该订单需要配送的体积。从货车表知得知有哪些类型的货车可以使用，得到了以上数据，就能解决我们的第一个问题：货物装载问题。
使用Map作为存储的数据结构，key值为当前的体积，value值为构成这个体积的最少用车集合，实现动态规划求解货物装载问题的具体过程为先初始化一个map，key为0，value为””，循环遍历这个map的key，如果存在值，用这个值加货车的体积，就是新key，判断新key是否已经有value，如果没有value为旧key的value+货车的体积，中间用”,”分隔，如果有，将这个新value和老value进行比较，看哪一种“，”少，因为，少说明用车少，成本少，加到key值超过我们需要的货物总体积后遍从换到下一个货车，直到把货车遍历完，拿到最小值，取他的value就是我们的装配方案，关键代码如下图3-4,3-5所示:
图3-4 解决装配问题的核心算法
图3-5 解决装配问题的核心算法
拿到货车的具体安排后，根据具体安排和从数据库拿到的各种数据，即可使用区域划分解决本系统的路径规划问题，具体解决方案如下:
使用Map作为存储地点区域的集合，key值为角度值，例如”0,10”表示是与起点夹角（与x轴正向所成的角度）,value值为地点区域的集合，一个键值对就表示与起点夹角为几度到几度的区域内的所有配送点。将从数据库拿到的所有地点放入到Map中后，通过遍历map的key，得到key所对应的value，得到当前区域的该配送的体积，如果大于起送体积，就通过计算各个点之间的距离，将各个点进行排序，根据顺序开始配送，如果小于就换成下一个key，当key遍历完成后，查看是否有剩余货物没被配送，若没有则结束，若有则将角度加大10度，重复上述操作，直到货物全部配送完全为止。关键代码，如下图所示：
图3-6 解决区域划分问题的核心算法
图3-7 解决区域划分问题的核心算法
package com.dwy.logistics.controller; import com.dwy.logistics.model.dto.front.CarFrontDTO; import com.dwy.logistics.model.dto.front.PlaceFrontDTO; import com.dwy.logistics.model.dto.front.RouteFrontDTO; import com.dwy.logistics.model.dto.front.TransportFrontDTO; import com.dwy.logistics.service.IFrontService; import com.dwy.logistics.service.IOrdersService; import lombok.extern.slf4j.Slf4j; import org.springframework.format.annotation.DateTimeFormat; import org.springframework.web.bind.annotation.GetMapping; import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.RequestParam; import org.springframework.web.bind.annotation.RestController; import javax.annotation.Resource; import java.util.Date; import java.util.List; /** * @Author: znz * @Date: 2022/8/12 15:42 */ @RestController @Slf4j @RequestMapping("/front") public class FrontController { @Resource IFrontService frontService; @GetMapping("/place") public List<PlaceFrontDTO> getPlaceFrontDTO(@RequestParam("date") @DateTimeFormat(pattern = "yyyy-MM-dd") Date date){ return frontService.getPlaceFrontDTO(date); } @GetMapping("/car") public List<CarFrontDTO> getCarFrontDTO(@RequestParam("date") @DateTimeFormat(pattern = "yyyy-MM-dd") Date date){ return frontService.getCarFrontDTO(date); } @GetMapping("/transport") public List<TransportFrontDTO> getTransportFrontDTO(@RequestParam("date") @DateTimeFormat(pattern = "yyyy-MM-dd") Date date){ return frontService.getTransportFrontDTO(date); } @GetMapping("/route") public List<RouteFrontDTO> getRouteFrontDTO(@RequestParam("date") @DateTimeFormat(pattern = "yyyy-MM-dd") Date date){ return frontService.getRouteFrontDTO(date); } }
package com.dwy.logistics.service.impl; import com.dwy.logistics.consts.CONST; import com.dwy.logistics.model.dto.distance.report.CarRouteReportDTO; import com.dwy.logistics.model.dto.distance.report.TruckRouteReportDTO; import com.dwy.logistics.model.dto.distance.PathDTO; import com.dwy.logistics.model.dto.front.PlaceFrontDTO; import com.dwy.logistics.model.dto.place.PlaceDTO; import com.dwy.logistics.service.IPlaceDTOService; import com.dwy.logistics.service.IRouteService; import lombok.extern.slf4j.Slf4j; import org.springframework.stereotype.Service; import javax.annotation.Resource; import java.util.List; /** * @Author: znz * @Date: 2022/8/4 16:52 */ @Service @Slf4j public class RouteServiceImpl extends AbstractServiceImpl implements IRouteService { @Resource IPlaceDTOService placeService; @Override public double getTrunkMinDistance(PlaceDTO startPlace, PlaceDTO endPlace, int size) { //https://restapi.amap.com/v4/direction/truck?parameters TruckRouteReportDTO truckRouteReportDTO = sendGet("https://restapi.amap.com/v4/direction/truck?key="+ CONST.GAODE_MAP_KEY+"&origin="+startPlace.getLocation()+"&originid="+startPlace.getId()+"&destination="+endPlace.getLocation()+"&destinationid="+endPlace.getId()+"&size="+size) .toJavaObject(TruckRouteReportDTO.class); List<PathDTO> paths = truckRouteReportDTO.getData().getRoute().getPaths(); return getMinDistance(paths); } @Override public double getCarMinDistance(PlaceDTO startPlace, PlaceDTO endPlace) { CarRouteReportDTO carRouteReportDTO = sendGet("https://restapi.amap.com/v3/direction/driving?key="+ CONST.GAODE_MAP_KEY+"&origin="+startPlace.getLocation()+"&originid="+startPlace.getId()+"&destination="+endPlace.getLocation()+"&destinationid="+endPlace.getId()+"&strategy="+"10") .toJavaObject(CarRouteReportDTO.class); List<PathDTO> paths = carRouteReportDTO.getRoute().getPaths(); return getMinDistance(paths); } @Override public double getCarMinDistance(String startPlaceID, String endPlaceID) { PlaceDTO startPlace = placeService.getPlaceDTOByID(startPlaceID); PlaceDTO endPlace = placeService.getPlaceDTOByID(endPlaceID); return getCarMinDistance(startPlace,endPlace); } @Override public double getCarMinDistance(PlaceFrontDTO startPlace, PlaceFrontDTO endPlace) { String url = "https://restapi.amap.com/v3/direction/driving?key="+ CONST.GAODE_MAP_KEY+"&origin="+startPlace.getLng()+","+startPlace.getLat()+"&destination="+endPlace.getLng()+","+endPlace.getLat()+"&strategy="+"10"; log.info("url:"+url); CarRouteReportDTO carRouteReportDTO = sendGet(url) .toJavaObject(CarRouteReportDTO.class); List<PathDTO> paths = carRouteReportDTO.getRoute().getPaths(); return getMinDistance(paths); } private double getMinDistance(List<PathDTO> paths){ double minDistance = paths.get(0).getDistance(); for (int i = 1 ; i <paths.size() ; i++){ if (minDistance > paths.get(i).getDistance()) { minDistance = paths.get(i).getDistance(); } } return minDistance; } }
package com.dwy.logistics.service.impl; import com.dwy.logistics.mapper.PlaceMapper; import com.dwy.logistics.model.dto.place.PlaceDTO; import com.dwy.logistics.model.entities.Place; import com.dwy.logistics.model.entities.PlaceKey; import com.dwy.logistics.service.IPlaceDTOService; import com.dwy.logistics.service.IPlaceService; import lombok.extern.slf4j.Slf4j; import org.springframework.stereotype.Service; import javax.annotation.Resource; /** * @Author: znz * @Date: 2022/8/5 17:52 */ @Service @Slf4j public class PlaceServiceImpl implements IPlaceService { @Resource PlaceMapper placeMapper; @Resource IPlaceDTOService placeDTOService; @Override public Place selectPlaceByID(String id) { PlaceKey placeKey = new PlaceKey(); placeKey.setUid(id); return placeMapper.selectByPrimaryKey(placeKey); } @Override public int insertPlace(Place place) { log.debug("insertPlace:"+place.toString()); return placeMapper.insert(place); } @Override public int insertPlaceByName(String keywords, String cityName) { log.debug("insertPlaceByName,keywords:"+keywords+",cityName:"+cityName); PlaceDTO placeDTO = placeDTOService.getFirstPlaceDTO(keywords, cityName); Place place = PlaceDTOToPlace(placeDTO); log.debug("insertPlaceByName:"+place.toString()); return placeMapper.insert(place); } @Override public int deletePlace(String id) { PlaceKey placeKey = new PlaceKey(); placeKey.setUid(id); return placeMapper.deleteByPrimaryKey(placeKey); } private Place PlaceDTOToPlace(PlaceDTO placeDTO){ Place place = new Place(); String s[] = placeDTO.getLocation().split(","); place.setUid(placeDTO.getId()); place.setLat(Double.parseDouble(s[1])); place.setLng(Double.parseDouble(s[0])); place.setName(placeDTO.getName()); return place; } }
五，项目总结
由于本系统实现的是物流拼单系统，是一个结合现实，且订单可以拆分的系统。本系统主要解决的是多车、多车型、一维约束、无时间约束、单目标优化的VFP问题和具有容量约束，多车型约束，目标函数为满载且路径短的VRP问题。经过分析，可以得到本系统的问题描述为：已知当日订单，包含了起点和终点以及配送货物的种类、体积和数量，可以获得当日需要配送的总体积为，和货车体积集合，货车不限制使用。求如何派车能够实现最大装载率，在装载率相同的情况下，如何使配送路径（不考虑回程）最短。
解决该问题有2个步骤：1、通过算法求解如何派出货车，使得货车的总体积大于货物的总体积，且满载率（满载率=货物的总体积/货车的总体积）最大。2、通过算法求解已知派出哪些货车，如何安排这些货车成功送完所有客户，配送路程最短。
