Conceptual model for the parallelized IPDP solver Sample Clauses

Conceptual model for the parallelized IPDP solver. ‌ As seen from figure 7 the parallelized parts of the IPDP solver is chosen to be 1) The xxxx search procedure for the IPDP with parallelized neighborhood exploration, and 2) A post-optimizer for the incumbent routes. A parallel implementation of the Xxxxx heuristic, was also implemented, but was abandoned because it gave no speedup compared to the serial implementation. The post-optimizer is chosen to be a 2-OPT intra route improvement heuristic for the VRP. The post-optimizer task starts up as an asynchronous task along with the IPDP task. The post-optimizer blocks until a route has been pushed onto a queue. The blocking mode means that the task waits until there is something to optimize. It always runs in the background. When the task is in blocking mode it does not use any CPU. There are 3 steps in the figure. The first step creates the objects that are used as shared memory, and starts the two tasks. The second step shows how the communication works. When the IPDP solver finds a feasible solution and it is set as the new best, the routes are added to a queue. When routes are added, the 2-OPT task will remove these routes from the queue and start to optimize them. After the optimization is done, the routes are added to another queue, and the task goes back to the waiting state. After the IPDP solver has added the routes to the queue, it continues the xxxx search to find a new best move. After the new move is applied, the second queue is checked to see if it contains any routes. If there are any routes present, the IPDP task will take the routes out and apply them to the incumbent routes and the current routes. The search and optimization continues until the stopping criterion is met. Step 3 prints out the solution information. Since these two tasks run asynchronously they must be synchronized before any attempt to combine the results. This must be done to make sure that the xxxx search procedure has not updated the incumbent solution while the post-optimizer ran. If the incumbent solution still remains the same, the improved routes from the post-optimizer is merged with the incumbent solution. The optimized routes are also added to the current solution, if the routes in the current solution have not been altered. If routes have been altered since optimization started, they could make the customers inventory and deliveries infeasible. The reason the solver only merges the optimized routes if the incumbent solution has not changed, is that there are many...