The traditional Capacitated Vehicle Routing Problem (CVRP) minimizes the total distance of the routes under the capacity constraints of the vehicles. But more often, the objective involves multiple criteria including not only the total distance of the tour but also other factors such as travel costs, travel time, and fuel consumption.Moreover, in reality, there are numerous implicit preferences ingrained in the minds of the route planners and the drivers. Drivers, for instance, have familiarity with certain neighborhoods and knowledge of the state of roads, and often consider the best places for rest and lunch breaks. This knowledge is difficult to formulate and balance when operational routing decisions have to be made. This motivates us to learn the implicit preferences from past solutions and to incorporate these learned preferences in the optimization process. These preferences are in the form of arc probabilities, i.e., the more preferred a route is, the higher is the joint probability. The novelty of this work is the use of a neural network model to estimate the arc probabilities, which allows for additional features and automatic parameter estimation. This first requires identifying suitable features, neural architectures and loss functions, taking into account that there is typically few data available. We investigate the difference with a prior weighted Markov counting approach, and study the applicability of neural networks in this setting.
翻译:传统的机动车辆脱轨问题(CVRP)将车辆能力限制下路线的总距离降到最低,但更经常的是,目标涉及多种标准,不仅包括旅行总距离,还包括旅行费用、旅行时间和燃料消耗等其他因素。 事实上,路线规划者和司机的头脑中有许多隐含的偏好。例如,司机熟悉某些街区,了解道路状况,常常考虑休息和午餐休息的最佳地点。当必须作出操作性路线决定时,这种知识很难形成和平衡。这促使我们学习过去解决办法的隐含偏好,并将这些学到的偏好纳入优化进程。这些偏好的形式是概率的,即更倾向于路线。例如,联合概率更高。这项工作的新颖之处是使用神经网络模型来估计异常的概率,从而能够增加特性和自动参数估计。这首先需要确定过去解决办法中隐含的偏好偏好之处,并将这些学到的偏好偏好纳入优化过程。这些偏好的形式是,即路线更可取的方式是,即,更可取的路线是联合的可能性。这项工作的新之处是使用神经网络模型来估计异常的概率,从而可以产生更多的特征和自动参数估计。这首先需要确定适当的适用性,先进行我们的研究。