车辆路径问题

车辆路线问题是一个规划过程，其中（运输）订单被分组到旅游中并按顺序放置。 通常，游览是由人或车辆进行的。 这个计划过程在所有需要计划大量订单和旅游的领域都很重要。 示例是零售商分支机构的交付、邮件的收集、垃圾的收集、人员的运输和服务人员的部署。 在快递-快递-包裹服务等常规路线的情况下，以这种方式形成运输网络结构。

订单通常包括将一定数量的货物从起点运送到目的地。 车辆路径问题的解决方案通常有两个方面：

• 聚类表明哪些订单被分组到一个旅游中
• 路线定义了行程中各点的服务顺序。

例如，车辆路径问题的目标是最小化使用的车辆数量、行驶距离、运行时间、二氧化碳排放量或更复杂的成本函数。 在标准的车辆路线问题问题中，所有起点或终点都在一个停车场，那里有有限或无限数量的相同车辆，但容量有限。 其他变体考虑额外的限制，例如 B. 时间窗口、多个站点或任意起点和终点（所谓的取件和送货问题）。

实际上，任务因许多限制而扩展。 例如，考虑多个仓库、异构车队或订单之间的优先级关系。 另一个可能的附加任务是考虑时间窗，车辆必须在该时间窗内到达客户，以符合由时间窗管理分配或预订的时段。 当订单情况在计划期间动态变化时，有人谈到动态车辆路径问题。

除了物流部门，在为客户提供服务的所有经济部门都有应用。 在许多公司中，车辆路线问题的软件用于编译生成的旅行并根据时间规范或重量限制以及运输成本等标准对其进行优化。

车辆路线问题的基本模型属于NP-hard问题类。 因此，启发式方法被用来解决问题。 简单的解决方法是节省启发式算法和扫描算法。 更好质量的解决方案基于进化算法、模拟冷却和禁忌搜索。 他们使用本地搜索策略，其中交换订单顺序或订单分配给车辆。 最近，蚂蚁算法也越来越多地被认为是一种解决问题的方法。

作为车辆路径问题的子问题，旅行商问题是通过考虑一辆无限容量的车辆并让它以最小的成本或距离行驶而产生的。

Def.: 将一组订单分配给一组运输工具，同时考虑距离和限制，以使使用运输工具和所覆盖的距离引起的所有总运输成本最小化。

车辆路径问题软件支持公司规划和优化旅游。 数字道路网络、客户主文件、车辆和驾驶员列表以及当前订单列表。 距离和旅行时间可以使用地理参考客户地址的坐标粗略估计或从远程工作中获取，或者用于路线优化的算法在数字道路网络上运行。 优化是通过将许多客户的运输要求组合成一个或多个旅行来进行的，这样可以观察到客户的时间规格、车辆负载和容量、司机休息和工作时间以及车辆维护周期，同时所产生的运输成本被最小化。 这些可能包括司机、调度员和车辆的固定成本，以及由消耗成本、通行费、维护和修理、工作时间和加班费组成的可变车队成本。