top of page

The Periodic Vehicle Routing Problem (PVRP) is widely used as a mathematical model for real-world problems, such as inventory servicing, periodic maintenance, and onsite service planning. Case studies can be found in milk collection, periodical grocery supply, waste collection, elevator maintenance, remote healthcare services and many others. 

The figure above shows a PVRP example. There are two vehicles avaliable, each with capacity c = 15 to deliver services to 7 customer (circles) over 2 days. Each day, each vehicle should strat and end its journey at the depot (square). The traveling duration and capacity constraint should be respected of building each vehicle's route.  Customers {1, 3, 5, 6} should be visited once and cusomters {2,4,7} should be visited every day during the planning period. The numbers in brackets represent the demand each customer requires at each visit.  The PVRP objective is to design a set of daily routes, that minimises the total travelling cost and satisfies the PVRP constraints.

  • Periodic vehicle routing problems 
-Data files-

In paper Chen, Y., Mourdjis, P., Polack, F., Cowling, P.(2016). Evaluating hyperheuristics and local search operators for period routing problem, we added 6 PVRP instances based on real-world gully-pot location information. Data format is described as follows:

The first line contains the following information: problem_type m n t

  • problem type:

    • 1 (PVRP)

  • m: number of vehicles

  • n: number of customers

  • t: number of days

 

The second line contains the following information for each customers: i x y d q f a list

  • i: customer ID

  • x: x coordinate

  • y: y coordinate

  • d: service duration

  • q: demand

  • f: frequency of visit

  • list: list of all possible visit combinations

In the files, each visit combination is coded with the decimal equivalent of the corresponding binary bit string. For example, in a 5-day period, the code 10 which is equivalent to the bit string 01010 means that a customer is visited on days 2 and 4. (Days are numbered from left to right.)

​

Here we provide 6 small maps generated based on real-world gully-pot-locations. They are all strongly structured. Then we artifically assign other factors such as visit frequency and service duration to each gully pot due to the confidential problem of the orginal data.

​

  -The real-world instances: 

​

  -Best found results for the 6 instances: 

​

More PVRP problems can be found from Periodic VRP Instances

  • Geographically distributed asset maintenance (GDMP)

In paper Chen, Y., Cowling, P., Polack, F., Mourdjis, P. (2016). A multi-arm bandit neighbourhood search for routing and scheduling problems. Submitted to the Journal of Heuristics, we tested 5 GDMP instances. Data format is described as blow:

 

  • The original data is collected for a gully-pot system maintenance. The maintenance system records 28,294 points distributed over approximately 36.1km2. Here, we generate five problem instances of various sizes, by randomly selecting 10%, 25%, 50%, 75% and 100% of the points from the system. Each gully pot is associated with risk impact r_i, the number of days since its last service, and two parameters for the failure probability estimation function P_i(d).

  • Each instance contains two files: 1) assets information file 2) distances matrix.

  • The depot ID=0;

    • 1) asset information file 

      • ​Each line contains an asset information: ID, risk impact r_i, lambda value of Weibull distribution, alph value of Weibull distribution, days since last visit d.

      • The probability of an asset i in its failed state on day d can be estimated by 

    • 2) distance matrix​

      • The column and row index is corresponding to the asset ID in the asset information file 

More information can be found in chapter 3 and chapter 8 of my thesis:

Computer Science

University of York

By Yujie Chen, 2016

bottom of page