Solving two-stage stochastic route-planning problem in milliseconds via end-to-end deep learning
Open Access
- 14 February 2021
- journal article
- research article
- Published by Springer Nature in Complex & Intelligent Systems
- Vol. 7 (3) , 1207-1222
Abstract
With the rapid development of e-economy, ordering via online food delivery platforms has become prevalent in recent years. Nevertheless, the platforms are facing lots of challenges such as time-limitation and uncertainty. This paper addresses a complex stochastic online route-planning problem (SORPP) which is mathematically formulated as a two-stage stochastic programming model. To meet the immediacy requirement of online fashion, an end-to-end deep learning model is designed which is composed of an encoder and a decoder. To embed different problem-specific features, different network layers are adopted in the encoder; to extract the implicit relationship, the probability mass functions of stochastic food preparation time is processed by a convolution neural network layer; to provide global information, the location map and rider features are handled by the factorization-machine (FM) and deep FM layers, respectively; to screen out valuable information, the order features are embedded by attention layers. In the decoder, the permutation sequence is predicted by long-short term memory cells with attention and masking mechanism. To learn the policy for finding optimal permutation under complex constraints of the SORPP, the model is trained in a supervised learning way with the labels obtained by iterated greedy search algorithm. Extensive experiments are conducted based on real-world data sets. The comparative results show that the proposed model is more efficient than meta-heuristics and is able to yield higher quality solutions than heuristics. This work provides an intelligent optimization technique for complex online food delivery system.Keywords
Funding Information
- National Science Fund for Distinguished Young Scholars of China (61525304)
- National Natural Science Foundation of China (61873328)
This publication has 23 references indexed in Scilit:
- DeepFM: A Factorization-Machine based Neural Network for CTR Prediction2017
- A parallel cooperative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problemSoft Computing, 2016
- Deep Residual Learning for Image Recognition2016
- Representation Learning: A Review and New PerspectivesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2013
- A parallel 2-opt algorithm for the Traveling Salesman ProblemFuture Generation Computer Systems, 1995
- TSPLIB—A Traveling Salesman Problem LibraryINFORMS Journal on Computing, 1991
- Optimal unsupervised learning in a single-layer linear feedforward neural networkNeural Networks, 1989
- Technical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman ProblemOperations Research, 1983
- A heuristic algorithm for the m-machine, n-job flow-shop sequencing problemOmega, 1983
- Stochastic Approximation Methods for Constrained and Unconstrained Systems1978