This paper expands on previous machine learning techniques applied to combinatorial optimisation problems, to approximately solve the capacitated vehicle routing problem (VRP). We leverage the versatility of graph neural networks (GNNs) and extend the application of graph convolutional neural networks, previously used for the Travelling Salesman Problem, to address the VRP. Our model employs a supervised learning technique, utilising solved instances from the OR-Tools solver for training. It learns to provide probabilistic representations of the VRP, generating final VRP tours via non-autoregressive decoding with beam search. This work shows that despite that reinforcement learning based autoregressive approaches have better performance, GNNs show great promise to solve complex optimisation problems, providing a valuable foundation for further refinement and study.

To enhance the perceived quality of home delivery services more and more flexibility is offered to the receivers. Enabling same-day delivery, communicating predefined narrow time windows, choosing the time windows and alternative address delivery add to the receiver’s experience, making the delivery company an interesting partner for parcel-shipping companies. A new flexibility is the possibility to change the chosen or communicated time window by the receiver during the day of delivery. In this paper we investigate the effect on delivery costs of this flexibility. Receivers are allowed to change their time window until the start of the old or new (the earliest) time window. In this paper two situations are investigated: one situation where communicated time window is a result of the planning process (Time Indication) and one situation where the original time window was already chosen by the receiver (Time choice). We show that the costs rises quickly in the Time Indication case when the percentage of time window changes grow. The Time Choice case is more costly at the start, but time window changes can be handled without (too much) extra costs. However, here a higher percentage of parcels is delivered outside the time windows.

In this paper Time-stamp Stochastic Assignment Problems are studied. These problems occur in places where an incoming request or task has to be connected to a resource immediately. A definition and framework for these problems is given, in which the different Time-stamp Stochastic Assignment Problems can be categorised. An explicit notation is introduced to distinguish the different categories. Several solution methods for Time-stamp Stochastic Assignment Problems are listed and their advantages and disadvantages are discussed.

In this paper we present the Dynamic Assignment Vehicle Routing Problem. This problem arises in parcel to vehicle assignment where the destination of the parcels is not known up to the assignment of the parcel to a delivering vehicle. The assignment has to be done immediately without the possibility of re-assignment afterwards. The problem is defined and various methods are proposed to come to an efficient solution method. Three cases are presented to test this efficiency. An approach using minimum cost insertion with penalty performs best.

In this paper we present a modification to the Dynamic Assignment Vehicle Routing Problem. This problem arises in parcel to vehicle assignment where the destination of the parcels is not known up to the assignment of the parcel to a delivering route. The assignment has to be done immediately without the possibility of re-assignment afterwards. We extend the original problem with a generalisation of the definition of capacity, with an unknown workload, unknown number of parcels per day, and a generalisation of the objective function. This new problem is defined and various methods are proposed to come to an efficient solution method.