Bi-objective orienteering for personal activity scheduling

We propose and solve a rich, bi-objective extension of the orienteering problem with time windows (OPTW) to model a combined routing and scheduling problem. Our research is motivated by the problem faced by mobile freelancers who have to integrate irregular appointments and tasks into their daily rou- tines. Those people have a number of tasks which they need to perform at various locations (e.g. meet- ings with different clients), subject to varying time constraints (e.g. opening hours), and with different levels of importance or urgency (e.g. submitting a deliverable versus cleaning the home office). Further- more, sets of related tasks may be subject to precedence relations and time dependencies. We explic- itly consider the trade-offbetween planning more tasks and enjoying more free time by means of a bi-objective model. The extension of the OPTW and the bi-objective formulation result in the Personal Planning Problem (PPP). We present a mathematical formulation of the PPP and a metaheuristic based on Large Neighborhood Search (LNS) is developed to generate a set of non-dominated solutions to the problem. Solution quality is analyzed on real-world-inspired test instances. Exact reference sets based on a linear single-commodity flow model are used as benchmarks. Extensive computational experiments show that the proposed metaheuristic generates near-optimal solution sets and scales well to larger in- stances.