In this issue we present a peer-reviewed selection of short papers that were accepted for presentation in the 4th International Conference on Variable Neighborhood Search (ICVNS'16) which was held in Málaga, Spain, during October 3–5, 2016. This conference is devoted to the Variable Neighborhood Search metaheuristic which was originally proposed by Nenad Mladenović and Pierre Hansen. This methodology is currently consolidated as a general framework to solve hard optimization problems and it is widely used all around the world.